Inducción matemática

Inducción matemática

1. Definición

   • La inducción matemática es un método de demostración que se utiliza cuando se trata de establecer la veracidad de una lista infinita de proposiciones. El método es bastante natural para usarse en una variedad de situaciones en la ciencia de la computación.
     • Algunas aplicaciones tienen un sabor muy matemático, tal como verificar que todo entero positivo satisface cierta fórmula. Otra utilización frecuente es la de demostrar que un programa de computación o que un algoritmo con ciclos funciona como se espera.

2. Principio de inducción

   • Consideremos una lista de proposiciones P(1), P(2), P(3), ... con índices en los Z+. Todas las proposiciones P(n) son verdaderas a condición que:
     • (B) P(1) sea verdadera.
       • (I) P(n + 1) es verdadera siempre que P(n) lo sea.
         • Nos referimos a (B), es decir al hecho de P(1) es verdadera, como la base de la inducción y nos referimos a (I) como el paso inductivo. En la notación del calculo proposicional (I) equivale decir que: La implicación P(n) ---> P(n + 1) es verdadera ∀n∈Z+.

3. Componentes de una inducción

   • Una demostración por Induccion tiene dos pasos:
     • La base de la Inducción
       • Mostrar que la afirmación es cierta en el primer caso.
     • El paso de Inducción
       • Suponer que la afirmación es cierta en un caso, y mostrar que debe ser cierta en el siguiente caso.