4.3: Inducción completa

Existe otra formulación de inducción, donde el paso inductivo comienza con un conjunto de suposiciones en lugar de una sola suposición. Este método a veces se llama inducción completa o inducción fuerte.

Teorema 4.25. Dejar\(P(1), P(2), P(3), \ldots\) ser una secuencia de declaraciones, una por cada número natural. Supongamos que

1. \(P(1)\)es verdad, y
2. Para todos\(k \in \mathbb{N}\), si\(P(j)\) es cierto para todos\(j\in \mathbb{N}\) tal que\(j \leq k\), entonces\(P(k+1)\) es cierto.

Entonces\(P(n)\) es cierto para todos\(n\in\mathbb{N}\).

Obsérvese la diferencia entre la inducción ordinaria (Teoremas 4.2 y 4.9) y la inducción completa. Para el paso de inducción de la inducción completa, no sólo estamos asumiendo que eso\(P(k)\) es cierto, sino que\(P(j)\) es cierto para todos\(j\) desde 1 hasta\(k\). A pesar del nombre, la inducción completa no es más fuerte ni más potente que la inducción ordinaria. Cabe señalar que en cualquier momento la inducción ordinaria es una técnica de prueba apropiada, así es la inducción completa. Entonces, ¿cuándo debemos usar la inducción completa?

En el paso inductivo, necesitas llegar\(P(k+1)\), y debes preguntarte cuál de los casos anteriores necesitas llegar ahí. Si todo lo que necesitas, es la declaración\(P(k)\), entonces la inducción ordinaria es el camino a seguir. Si dos casos anteriores,\(P(k - 1)\) y\(P(k)\), son necesarios para alcanzar\(P(k + 1)\), entonces la inducción completa es apropiada. En el extremo, si uno necesita el rango completo de casos anteriores (es decir, todos los enunciados\(P(1), P(2),\ldots,P(k)\)), entonces nuevamente se debe utilizar la inducción completa.

Tenga en cuenta que en situaciones donde la inducción completa sea apropiada, podría darse el caso de que necesite verificar más de un caso en el escalón base. El número de casos base a verificar depende de cómo se necesite “mirar hacia atrás” en el paso de inducción.

Prueba de Esqueleto 4.26. Aquí está la estructura general para una prueba por inducción completa.

Se procede por inducción.

1. Paso base: [Verifica que\(P(1)\) sea cierto. Dependiendo de la declaración, también es posible que deba verificar que\(P(k)\) sea cierto para otros valores específicos de\(k\).]
2. Paso inductivo: [Tu objetivo es demostrar “Para todos\(k\in\mathbb{N}\), si para cada uno\(k \in \mathbb{N}\),\(P(j)\) es cierto para todos\(j\in \mathbb{N}\) tal que\(j \leq k\), entonces \(P(k+1)\)es cierto”.] Vamos\(k \in \mathbb{N}\). Supongamos que\(P(j)\) es verdad para todos\(j \leq k\). [Hacer algo para derivar que \(P(k+1)\)sea cierto.] Por lo tanto,\(P(k+1)\) es cierto.

Así, por inducción completa,\(P(n)\) es cierto para todos los enteros\(n \ge a\).

Al abordar los problemas en esta sección, piense detenidamente cuántos pasos base debe verificar.

Teorema 4.27. Defina una secuencia de números por\(a_1 = 1\)\(a_2 = 3\), y\(a_n = 3a_{n-1} - 2a_{n-2}\) para todos los números naturales\(n \geq 3\). Entonces\(a_n = 2^n - 1\) para todos\(n \in \mathbb{N}\).

Teorema 4.28. Defina una secuencia de números por\(a_1 = 3, a_2 = 5, a_3 = 9\), y\(a_n = 2a_{n-1} + a_{n-2}-2a_{n-3}\) para todos los números naturales\(n \geq 4\). Entonces\(a_n = 2^n + 1\) para todos\(n \in \mathbb{N}\).

Problema 4.29. La secuencia de Fibonacci viene dada por\(f_1=1\)\(f_2=1\), y\(f_n=f_{n-1}+f_{n-2}\) para todos los números naturales\(n \geq 3\). \(\left(\frac{3}{2}\right)^{n-2}\leq f_n\leq 2^n\)Demuéstralo para todos\(n\in\mathbb{N}\).

Recordemos que el Teorema 4.9 generalizó el Teorema 4.2 y nos permitió manejar situaciones donde el caso base era algo distinto a\(P(1)\). Podemos generalizar la inducción completa de la misma manera, pero no vamos a anotar esto como teorema formal.

Problema 4.30. Demostrar que cada cantidad de franqueo que sea de al menos\(12\) centavos se puede hacer a partir de sellos de\(4\)\(5\) -cent y -cent.

Problema 4.31. Los whoziwhatzits vienen en cajas de 6, 9 y 20. Demostrar que para cualquier número natural\(n \geq 44\), es posible comprar exactamente\(n\) Whoziwhatzits con una combinación de estas cajas.

Problema 4.32. Considera una cuadrícula de cuadrados que sea\(2\) cuadrados anchos y\(n\) cuadrados largos. Usando\(n\) dominó que son\(1\) cuadrados por\(2\) cuadrados, hay muchas formas de cubrir perfectamente este tablero de ajedrez sin superposición. ¿Cuántos? Demuestra tu respuesta.

Problema 4.33. Una cadena binaria de longitud\(n\) es una lista ordenada de\(n\) dígitos tal que cada dígito es 0 o 1. Por ejemplo\(011101\) y\(011011\) son cadenas binarias distintas de longitud 6. Estas son las reglas para el Solitario Binario: En cualquier etapa, se le permite:

1. Intercambia el dígito más a la izquierda (es decir, cambiar de 0 a 1, o de 1 a 0). Por ejemplo, podemos hacer\(011101\to 11101\).
2. Cambie el dígito inmediatamente a la derecha de la ocurrencia más a la izquierda de 1. Por ejemplo, podemos hacer\(011011\to 010011\).

Demuestre que para todos\(n\in\mathbb{N}\), puede cambiar cualquier cadena binaria de longitud\(n\) a cualquier otra cadena binaria de la misma longitud.

Problema 4.34. Demostrar que el número de cadenas binarias de longitud\(n\) que nunca tienen dos 1's consecutivos es el número de Fibonacci\(f_{n+2}\). Ver Problema 4.29 para la definición de los números de Fibonacci.