La clave para analizar muchos problemas computacionales y matemáticos radica en una técnica llamada inducción. ¿Cómo poder cerciorarse de que un algoritmo funcionará siempre para cualquier entrada que se le proporcione, independientemente del tamaño de ésta? Es usual en los algoritmos repetir un procedimiento una y otra vez hasta encontrar el resultado que se busca. La idea es probar que si el algoritmo funcionó bien hasta cierto punto, es decir, después de ejecutar el procedimiento cierto número de veces (n), al repetir el procedimiento una vez más (+1), seguirá trabajando bien, habiendo repetido el procedimiento n + 1 veces.
Curiosidades
El Día del Dominó es un evento anual organizado por Robin Paul Weijers en Holanda, donde se construyen caminos de fichas de dominó, de manera que vayan cayendo una por una. En la celebración de 2006 los participantes que obtuvieron el récord mundial lograron colocar 4 400 000 fichas de las cuales cayeron 4 079 381.
El argumento inductivo descrito en el párrafo anterior alude a lo que sucede cuando se colocan fichas de dominó en fila…
y se tira la primera ficha.
Se sabe que se caerán todas porque:
1] Si se empuja una ficha se cae.
2] Si una ficha se cae y está colocada correctamente junto a la ficha que le sigue, esta última también se caerá.
A partir de estos dos hechos se concluye que todas las fichas se caerán.
A continuación se mostrarán algunos ejemplos de cómo se utiliza un argumento de inducción para probar que un enunciado se cumple para todo valor de n, n =1, 2…
