3.8: Pruebas por Inducción
- Page ID
- 118572
Ninguna discusión sobre la recursión y la inducción estaría completa sin algunos ejemplos obligatorios de pruebas usando inducción. Empezamos con el ejemplo de “Hola Mundo”.
Por cada entero positivo\(n\), la suma de los primeros enteros\(n\) positivos es\(n(n+1)/2\), es decir,
\(\displaystyle \sum_{i=1}^n i = \frac{n(n+1)}{2}\).
Para nuestra primera versión de un comprobante de la Proposición 3.12, identificamos claramente la declaración abierta\(S_n\) y describimos la prueba cuidadosamente en términos de\(S_n\). A medida que desarrolles más experiencia en la redacción de pruebas por inducción, esto se volverá menos esencial, como verás en la segunda versión de la prueba.
- Prueba.
-
Dejar\(n\) ser un entero positivo, y dejar\(S_n\) ser la sentencia abierta
\(\displaystyle \sum_{i=1}^n i = \dfrac{n(n+1)}{2}\).
Demostraremos que\(S_n\) es cierto para todos los enteros positivos por inducción. Para el paso base, debemos demostrar que\(S_1\) es cierto. Cuando\(n=1\), el lado izquierdo de\(S_n\) es solo 1, mientras que el lado derecho evalúa a\(1(1+1)/2=1\). Por lo tanto,\(S_1\) es cierto.
A continuación asumimos que para algún entero positivo\(k\),\(S_k\) es cierto. Es decir, asumimos
\(\displaystyle \sum_{i=1}^k i = \dfrac{k(k+1)}{2}\).
Ahora buscamos demostrar que eso\(S_{k+1}\) es cierto, y comenzar por considerar el lado izquierdo de\(S_{k+1}\). Notamos que
\(\displaystyle \sum_{i=1}^{k+1} i = (\sum_{i=1}^k i) + (k+1) = \dfrac{k(k+1}{2} + (k+1)\),
ya que nuestra hipótesis inductiva que\(S_k\) es verdadera nos da la fórmula más simple para la suma. Ahora continuando con un poco de álgebra, encontramos
\(\dfrac{k(k+1)}{2} + (k+1) = \dfrac{k^2+3k+2}{2} = \dfrac{(k+1)(k+2)}{2}\).
Por lo tanto,\(S_{k+1}\) es cierto. Ya que hemos demostrado que eso\(S_1\) es cierto y que por cada entero positivo\(k\), si\(S_k\) es cierto, entonces\(S_{k+1}\) es cierto, concluimos que\(S_n\) es cierto para todos los enteros positivos\(n\) por el Principio de Inducción Matemática.
Antes de mirar una versión refinada de esta prueba, tomemos un momento para discutir los pasos clave en cada prueba por inducción. El primer paso es el paso base, en el que se demuestra que la declaración abierta\(S_1\) es verdadera. (Vale la pena señalar que aquí no hay nada de especial en 1. Si queremos demostrar solo que eso\(S_n\) es cierto para todos los enteros\(n \geq 5\), entonces probar que\(S_5\) es cierto es nuestro paso base.) Al probar el paso base, si\(S_n\) es una ecuación, no solo escribimos\(S_1\) y seguimos adelante. Tenemos que demostrar que eso\(S_1\) es cierto. Observe cómo en la prueba anterior, discutimos el lado izquierdo\(S_1\) y el lado derecho de\(S_1\) y concluimos que eran iguales.
Después del paso base viene el paso inductivo, en el que asumimos que eso\(S_k\) es cierto para algún entero positivo\(k\) y demostramos que\(S_{k+1}\) es cierto. Al hacer esto, llamamos a\(S_k\) nuestra hipótesis inductiva. En el paso inductivo, el error más común que cometen los estudiantes es comenzar con la totalidad\(S_{k+1}\) y manipularlo hasta obtener una declaración verdadera. Esto es peligroso, ya que es posible comenzar con algo falso y a través de pasos algebraicos válidos, obtener una declaración verdadera. En cambio, la mejor opción es trabajar como con el paso base: si\(S_{k+1}\) es una ecuación o desigualdad, trabajar por un lado hasta encontrar un lugar para aplicar la hipótesis inductiva y luego continuar hasta obtener el otro lado. Si el álgebra se vuelve complicado en el camino, también puede trabajar con el lado izquierdo de\(S_{k+1}\) y trabajar por separado con el lado derecho de\(S_{k+1}\). Si eres capaz de manipular ambos lados para que estén en la misma forma, entonces has demostrado que son iguales y\(S_{k+1}\) es verdad.
Ahora echemos un vistazo a una prueba más refinada de la Proposición 3.12. A partir de aquí, cuando demos una prueba por inducción, usaremos este estilo. A medida que estás comenzando con las pruebas de inducción, es posible que te resulte útil ser más explícito sobre los pasos como hicimos en la primera prueba anterior.
- Prueba.
-
Primero probamos la aserción cuando\(n=1\). Para este valor de\(n\), el lado izquierdo es solo 1, mientras que el lado derecho evalúa a\(1(1+1)/2 = 1\).
Ahora supongamos que para algún entero positivo\(k\), la fórmula se mantiene cuando\(n=k\), es decir, asumir que
\(\displaystyle \sum_{i=1}^k i = \dfrac{k(k+1)}{2}\).
Entonces se deduce que
\(\displaystyle \sum_{i=1}^{k+1} i = (\sum_{i=1}^k i) + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k^2+3k+2}{2} = \dfrac{(k+1)(k+2)}{2}\).
Así la fórmula también se mantiene cuando\(n=k+1\). Por el Principio de Inducción Matemática, se mantiene para todos los enteros positivos\(n\).
Los argumentos anteriores son 100% correctos... pero algunos matemáticos combinatorios argumentarían que en realidad pueden ocultar lo que realmente está pasando. Estas personas preferirían mucho una prueba combinatoria, como se proporciona en la Sección 2.4. Nuestra perspectiva es que deberías preferir dar una prueba combinatoria, cuando puedes encontrar una. Pero si se presiona, deberías poder dar una prueba formal por inducción matemática.
Aquí hay un segundo ejemplo, también todo un clásico. Nuevamente, recordemos que dimos una prueba combinatoria en el último capítulo. Al leer la prueba, asegúrese de que puede identificar la declaración abierta\(S_n\), el paso base y el paso inductivo.
Para cada entero positivo\(n\), la suma de los primeros enteros positivos\(n\) impares es\(n^2\), es decir,
\(\displaystyle \sum_{i=1}^n (2i-1) = n^2\).
- Prueba
-
Esto lo demostraremos por inducción. Primero, tenga en cuenta que la fórmula sostiene cuándo\(n=1\). Ahora supongamos que\(k\) es un entero positivo y que la fórmula se mantiene cuando\(n=k\), es decir, asumir
\(\displaystyle \sum_{i=1}^k (2i-1) = k^2\).
Entonces
\(\displaystyle \sum_{i=1}^{k+1} (2i-1) = (\sum_{i=1}^k 2i-1) + 2k + 1 = k^2 + (2k+1) = (k+1)^2\).
Por lo tanto, la proposición sigue por el Principio de Inducción Matemática.
Aquí hay una versión más general del primer resultado en esta sección, y nuevamente notamos que dimos una prueba combinatoria en la Sección 2.4.
Dejar\(n\) y\(k\) ser enteros no negativos con\(n \geq k\). Entonces
\(\displaystyle \sum_{i=k}^n \dbinom{i}{k} = \dbinom{n+1}{k+1}\)
- Prueba
-
Se corrige un entero no negativo\(k\). Luego probamos la fórmula por inducción en\(n\). Si\(n=k\), tenga en cuenta que el lado izquierdo es justo\(\binom{k}{k} = 1\), mientras que el lado derecho es el\(\binom{k+1}{k+1}\) que también es 1. Ahora supongamos que\(m\) es un entero no negativo, con\(m \geq k\), y que la fórmula se mantiene cuando\(n=m\), es decir, asumir que
\(\displaystyle \sum_{i=k}^m \dbinom{i}{k} = \dbinom{m+1}{k+1}\).
Entonces
\(\displaystyle \sum_{i=k}^{m+1} \dbinom{i}{k} = \sum_{i=k}^m \dbinom{i}{k} + \dbinom{m+1}{k}\)
\(= \dbinom{m+1}{k+1} + \dbinom{m+1}{k}\)
\(= \dbinom{m+2}{k+1} \)
Por lo tanto, la proposición sigue por el Principio de Inducción Matemática.