Principio de inducción

Contenido

Principio de inducción#

Introducción#

En esta entrada supondremos que manejas el principio de inducción, por lo menos a un nivel básico. En caso de no ser así, te recomendamos revisar la siguiente entrada de blog: Introducción a principio de inducción.

Como quizás recuerdes, el principio de inducción permite hacer demostraciones matemáticas para una cantidad infinita de números, probando simplemente una cantidad finita de afirmaciones, usualmente dos. En su versión más básica dice lo siguiente:

Principio de inducción. Para mostrar que una afirmación \(P(n)\) es cierta para todo entero positivo \(n\) basta con:

Mostrar que \(P(1)\) es cierta.
Mostrar que para \(n\geq 1\), se tiene que \(P(n)\) implica \(P(n+1)\).

En esta entrada recordaremos cómo usar el principio de inducción en su versión básica y luego discutiremos variantes del principio de inducción que cumplen con el mismo objetivo, pero son más versátiles.

Principio de inducción básico#

Para recordar cómo se usa el principio de inducción resolvamos el siguiente problema.

Problema. Muestra que para todo entero \(n\) se cumple que

\[\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \ldots + \frac{1}{n\cdot (n+1)}=\frac{n}{n+1}\]

Solución. Hagamos una solución que use principio de inducción. Para ello, necesitamos comenzar verificando que la igualdad es cierta cuando \(n=1\). Luego, a partir de la veracidad de la igualdad para cierta \(n\), debemos demostrar la veracidad para \(n+1\).

La veracidad para \(n=1\) es sencilla de verificar, pues en lado izquierdo tendríamos únicamente al sumando \(\frac{1}{1\cdot 2} = \frac{1}{2}\), mientras que en el lado derecho tendríamos la expresión \(\frac{1}{2}\). Ambas expresiones son iguales.

Como hipótesis inductiva, supongamos la veracidad de la igualdad para cierto valor de \(n\). Aquí \(n\) es fijo, no estamos suponiendo la veracidad para todo \(n\), pues eso es lo que queremos mostrar. De esta manera, tenemos que

\[\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \ldots + \frac{1}{n\cdot (n+1)}=\frac{n}{n+1}.\]

Debemos mostrar la veracidad para \(n+2\), es decir, debemos mostrar que

\[\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \ldots + \frac{1}{n\cdot (n+1)} + \frac{1}{(n+1)(n+2)}=\frac{n+1}{n+2}.\]

Para ello, notemos que en el lado izquierdo aparece parte de la expresión de la hipótesis inductiva. Tenemos entonces:

\[\begin{align*} \left(\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \ldots + \frac{1}{n\cdot (n+1)}\right) + \frac{1}{(n+1)(n+2)} &= \frac{n}{n+1}+ \frac{1}{(n+1)(n+2)}\\ &=\frac{n(n+2)+(1)}{(n+1)(n+2)}\\ &=\frac{n^2+2n+1}{(n+1)(n+2)}\\ &=\frac{(n+1)^2}{(n+1)(n+2)}\\ &=\frac{n+1}{n+2}. \end{align*}\]

En la primera igualdad usamos la hipótesis inductiva. Luego, simplemente hicimos las operaciones con fracciones. Notemos que llegamos justo al lado derecho que queríamos llegar. Esto termina la prueba por inducción. \(\square\)

Inducción fuerte#

Existen variantes del principio de inducción que son igual de válidas. La siguiente se le conoce como el principio de inducción fuerte, pues en la hipótesis inductiva suponemos no solamente un caso, sino también todos los anteriores.

Principio de inducción fuerte. Para mostrar que una afirmación \(P(n)\) es cierta para todo entero positivo \(n\) basta con:

Mostrar que \(P(1)\) es cierta.
Mostrar que para \(n\geq 2\), todas las afirmaciones \(P(k)\) para \(k<n\) implican en conjunto \(P(n)\).

Veamos un problema interesante que hace uso de esta versión del principio de inducción.

Problema. Muestra que cualquier número entero positivo se puede expresar como suma de números de Fibonacci distintos.

Solución. Procedemos por inducción fuerte. En el caso base tenemos a \(1\), que ya es por sí mismo un número de Fibonacci, así que tiene una expresión como la que buscamos.

Tomemos ahora un entero \(n\geq 2\) y supongamos que todos los números desde \(1\) hasta \(n-1\) se pueden escribir como suma de Fibonacci distintos. Tomemos el entero \(k\) más grande posible tal que \(F_k<n\). Como \(k\) es el entero más grande para el cual esto pasa, tenemos que \(n\leq F_{k+1}=F_{k}+F_{k-1}\), de donde

\[n-F_k\leq F_{k-1}.\]

Como \(n\) es mayor que \(F_k\), se tiene que \(n-F_k\geq 1\). Además, \(n-F_k\lt n\). Por hipótesis inductiva, el número \(n-F_k\) se debe poder expresar como suma de números de Fibonacci distintos, digamos

\[n-F_k=F_{i_1}+F_{i_2}+\ldots+F_{i_r}.\]

Como

\[n-F_k\leq F_{k-1},\]

ninguno de los sumandos puede exceder a \(F_{k-1}\). Así, todos ellos son menores a \(F_k\). Por lo tanto, tenemos que

\[n=F_{i_1}+F_{i_2}+\ldots+F_{i_r}+F_k,\]

en donde en el lado derecho tenemos números de Fibonacci distintos, como queríamos. \(\square\)

La idea de usar inducción fuerte es muy buena: podemos demostrar cosas utilizando casos que ya hemos demostrado. Esta misma intuición la utilizaremos cuando diseñemos algoritmos recursivos. Mientras tanto, estudia el siguiente código para ver cómo llevamos la idea de la demostración anterior a un algoritmo que escribe a cualquier entero positivo como suma de Fibonaccis distintos.

def sum_fibo(n):
    fibo=[0,1]
    while fibo[-1]<n:
        fibo.append(fibo[-1]+fibo[-2])
    sumandos=[]
    suma=0
    for j in fibo[::-1]:
        if suma+j<=n:
            sumandos.append(j)
            suma+=j
            if suma==n:
                break

    print("El número {} es la suma de los Fibonaccis en la lista {}".format(n,sumandos))

sum_fibo(553)
sum_fibo(53)
sum_fibo(111)

El número 553 es la suma de los Fibonaccis en la lista [377, 144, 21, 8, 3]
El número 53 es la suma de los Fibonaccis en la lista [34, 13, 5, 1]
El número 111 es la suma de los Fibonaccis en la lista [89, 21, 1]

Inducción con base más grande#

Cuando en la demostración del paso inductivo usamos más de un elemento anterior, es importante que en los casos base revisemos tantos casos como la demostración de la hipótesis inductiva requiera. Para ver un ejemplo de esto, retomemos un ejemplo que dejamos pendiente acerca de cómo son los residuos al dividir entre \(3\) de los números de Fibonacci.

Problema. Los residuos de la sucesión de Fibonacci al dividir entre \(3\) se ciclan, con un ciclo de periodo \(8\) que es \(0,1,1,2,0,2,2,1\).

Demostración. Hacemos el caso base de manera computacional, calculando los primeros \(8\) números de la sucesión de Fibonacci y verificando que en efecto se cumple lo que decimos:

a,b=0,1
for j in range(8):
    print("Para {} el Fibonacci es {} y deja residuo {} al dividirse entre 3".format(j,a,a%3))
    a,b=b,a+b

Para 0 el Fibonacci es 0 y deja residuo 0 al dividirse entre 3
Para 1 el Fibonacci es 1 y deja residuo 1 al dividirse entre 3
Para 2 el Fibonacci es 1 y deja residuo 1 al dividirse entre 3
Para 3 el Fibonacci es 2 y deja residuo 2 al dividirse entre 3
Para 4 el Fibonacci es 3 y deja residuo 0 al dividirse entre 3
Para 5 el Fibonacci es 5 y deja residuo 2 al dividirse entre 3
Para 6 el Fibonacci es 8 y deja residuo 2 al dividirse entre 3
Para 7 el Fibonacci es 13 y deja residuo 1 al dividirse entre 3

Ahora demostraremos el resultado «en bloques de \(8\)». Así, para cierta \(n\geq 1\), supongamos que el resultado es cierto para los primeros \(8n\) números de Fibonacci (hasta \(F_{8n-1}\)). Lo que haremos en el paso inductivo es ver que para los siguientes \(8\) números de Fibonacci también es cierto.

Comencemos viendo que esto sucede para \(F_{8n}\), donde tenemos que ver que el residuo es \(0\).Usamos que que:

\[F_{8n}=F_{8n-1}+F_{8n-2}\]

Como por hipótesis inductiva tenemos que \(F_{8n-1}\) deja residuo \(1\) al dividirse entre \(3\) y \(F_{8n-2}\) deja residuo \(2\) al dividirse entre \(3\), tenemos que \(F_{8n}\) es múltiplo de \(3\), como queríamos. En notación de congruencias, podemos escribir esto así:

\[F_{8n}=F_{8n-1}+F_{8n-2}\equiv 1 + 2 \equiv 0 \pmod{3}.\]

De manera similar,

\[\begin{align*} F_{8n+1}&=F_{8n}+F_{8n-1}\equiv 0 + 1 \equiv 1 \pmod{3}\\ F_{8n+2}&=F_{8n+1}+F_{8n}\equiv 1 + 0 \equiv 1 \pmod{3}\\ F_{8n+3}&=F_{8n+2}+F_{8n+1}\equiv 1 + 1 \equiv 2 \pmod{3}\\ F_{8n+4}&=F_{8n+3}+F_{8n+2}\equiv 2 + 1 \equiv 0 \pmod{3}\\ F_{8n+5}&=F_{8n+4}+F_{8n+3}\equiv 0 + 2 \equiv 2 \pmod{3}\\ F_{8n+6}&=F_{8n+5}+F_{8n+4}\equiv 2 + 0 \equiv 2 \pmod{3}\\ F_{8n+7}&=F_{8n+6}+F_{8n+5}\equiv 2 + 2 \equiv 1 \pmod{3}\\ \end{align*}\]

Esto termina la prueba del paso inductivo y por lo tanto la demostración. \(\square\)

Tarea moral#

Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.

Si no somos cuidadosos con los argumentos inductivos, podemos tener problemas y demostrar cosas falsas. Considera el siguiente «argumento» inductivo que muestra que todos los gatos son del mismo color. Procedemos por inducción. Si tenemos un gato, sólo hay un color que verificar. Supongamos que ya verificamos que siempre que tenemos \(n\) gatos, entonces todos son del mismo color. Toma un conjunto \(X\) de \(n+1\) gatos y dos gatos \(G\) y \(H\) de \(X\). Si a \(X\) le quitamos el gato \(G\), por hipótesis inductiva todos son del mismo color. Si a \(X\) le quitamos el gato \(H\), por hipótesis todos son del mismo color. Así, \(G\) es del mismo color que los gatos de \(X\), que son del mismo color que \(H\), así que ya todos los \(n+1\) gatos fueron del mismo color. Esto termina la «demostración». ¿Cuál es el problema?
Considera la matriz \(A=\begin{pmatrix} 1 & 2 \\ 0 & 1\end{pmatrix}\). Encuentra a mano las matrices \(A^2\), \(A^3\), \(A^4\), \(A^5\). Obsérvalas con detenimiento. Conjetura una expresión cerrada para la matriz \(A^n\) y demuéstrala por inducción.
Regresa al capítulo de «Buscar un patrón», a la sección de «Triángulo de Pascal con saltos de tres en tres». Demuestra por inducción todas las observaciones que se hicieron para obtener la solución.
Muestra que cualquier número entero positivo se puede expresar de manera única como suma de números de Fibonacci distintos, en donde ademas no usamos dos números de Fibonacci \(F_n\) y \(F_m\) con \(n\) y \(m\) consecutivos.
Hay otra variante del principio de inducción que se llama «inducción de Cauchy». Revisa la siguiente entrada de blog para averiguar en qué consiste: Variantes del principio de inducción.