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
Mostrar que
es cierta.Mostrar que para
, se tiene que implica .
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
Solución. Hagamos una solución que use principio de inducción. Para ello, necesitamos comenzar verificando que la igualdad es cierta cuando
La veracidad para
Como hipótesis inductiva, supongamos la veracidad de la igualdad para cierto valor de
Debemos mostrar la veracidad para
Para ello, notemos que en el lado izquierdo aparece parte de la expresión de la hipótesis inductiva. Tenemos entonces:
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.
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
Mostrar que
es cierta.Mostrar que para
, todas las afirmaciones para implican en conjunto .
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
Tomemos ahora un entero
Como
Como
ninguno de los sumandos puede exceder a
en donde en el lado derecho tenemos números de Fibonacci distintos, como queríamos.
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
Problema. Los residuos de la sucesión de Fibonacci al dividir entre
Demostración. Hacemos el caso base de manera computacional, calculando los primeros
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
Comencemos viendo que esto sucede para
Como por hipótesis inductiva tenemos que
De manera similar,
Esto termina la prueba del paso inductivo y por lo tanto la demostración.
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
gatos, entonces todos son del mismo color. Toma un conjunto de gatos y dos gatos y de . Si a le quitamos el gato , por hipótesis inductiva todos son del mismo color. Si a le quitamos el gato , por hipótesis todos son del mismo color. Así, es del mismo color que los gatos de , que son del mismo color que , así que ya todos los gatos fueron del mismo color. Esto termina la «demostración». ¿Cuál es el problema?Considera la matriz
. Encuentra a mano las matrices , , , . Obsérvalas con detenimiento. Conjetura una expresión cerrada para la matriz 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
y con y 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.