6: Inducción y Recursión
- Page ID
- 114532
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Algunos problemas pueden resolverse (o contarse) más fácilmente con la ayuda de una secuencia definida de forma recursiva. Comenzaremos este capítulo introduciendo estas secuencias.
Debió haber visto pruebas básicas por inducción en al menos un curso previo. Las pruebas por inducción son una técnica matemática importante, y a menudo se utilizan en artículos publicados. Haremos una revisión rápida de las pruebas básicas por inducción, aplicándolas a secuencias definidas de forma recursiva. Luego tocaremos algunos usos ligeramente más sofisticados de la inducción. Las pruebas por inducción serán una técnica que usaremos a lo largo del resto del curso, en una variedad de contextos.
- 6.1: Secuencias definidas recursivamente
- Puede estar familiarizado con el término “recursión” como técnica de programación. Proviene de la misma raíz que la palabra “repetir”, y es una técnica que implica aplicar repetidamente una definición de autorreferencia hasta llegar a algunos términos iniciales que se definen explícitamente, y luego volver a través de las aplicaciones para elaborar el resultado que queremos. Si no seguiste eso, está bien, pasaremos por la definición y algunos ejemplos específicos que deberían darte la idea.
- 6.2: Inducción básica
- En una prueba por inducción, determinar que P (n0) es verdadero para algún entero particular n0 se llama el caso base. Demostrar la declaración condicional de que P (k) P (k+1) por cada k ≥ n0 se llama el paso inductivo. La suposición que hacemos en el paso inductivo, que P (k) es cierto para algunos k ≥ n0 arbitrarios, se llama la hipótesis inductiva, y puede ser referida por (IH) cuando se está utilizando en la prueba.
- 6.3: Inducción más avanzada
- Ahora que hemos revisado la forma básica de inducción, es importante considerar algunas formas más avanzadas que a menudo se utilizan. La primera forma que veremos es una fuerte inducción. Cuando tenemos una secuencia definida recursivamente que depende de los términos anteriores, a veces necesitamos saber no solo sobre el término único que viene inmediatamente antes del término n, sino sobre otros términos anteriores. Sólo juntando toda esta información podremos deducir el resultado que necesitamos sobre el enésimo término.
- 6.4: Resumen
- Esta página contiene el resumen de los temas tratados en el Capítulo 6.