2.4 PRINCIPIO DE INDUCCIÓN MATEMÁTICA

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 ceirta 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.

Primer principio de inducción matemática

Consideremos una lista de proposiciones p(1), p(2), p(3), ... con índices en los enteros positivos +. 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 +.

Ejemplo:
Demostrar (3k - 2) = 1/2(3n² - n) n +.

Demostración: La n-ésima proposición p(n) es verdadera, esto es

(3k - 2) = 1/2(3n² - n)

Notese que:

p(1) = 1 = 1/2[3(1)² - 1)] de aqui que 1 = 1
p(2) = 1 + 4 = 1/2[3(2)² - 2)] de aqui que 5 = 5
p(3) = 1 + 4 + 7 = 1/2[3(3)² - 3)] de aqui que 12 = 12
.
.
.

En particular, p(1) es verdadera por inspección y esto establece la base de la inducción. Ahora supongase que p(n) es verdadera para algún n, esto es:

(3k - 2) = 1/2(3n² - n)

necesitamos demostrar que p(n + 1)

(3k - 2) = 1/2[3(n + 1)² - (n + 1)]

tal como lo establece el paso inductivo.

Utilizando p(n) tenemos que

(3k - 2) = (3k - 2) + [3(k + 1) - 2]= 1/2(3k² - k) + (3k + 1)

para verificar p(n + 1) necesitamos comprobar que:

1/2(3k² - k) + (3k + 1) = 1/2[3(k + 1)² - (k + 1)]

Esto ya es un problema puramente algebraico, para lo cual se trabajara con el lado izquierdo de la igualdad, esto es:

1/2(3k² - k) + (3k + 1) = 1/2(3k² - k + 6k + 2)
  = 1/2(3k² + 5k + 2)
  = 1/2(3k + 2)(n + 1)
  = 1/2[3(k + 1) -1](k + 1)
  = 1/2[3(k + 1)² - (k + 1)]


Entonces p(n + 1) es verdadera siempre que p(n) lo sea. Por el primer principio de inducción matemática se concluye que p(n) es verdadera n +.

No siempre es necesario el uso del simbolo de sumatoria para aplicar la inducción matemática, puede también utilizarse parte del desarrollo de la misma, como lo muestra el siguiente:

Ejemplo:
Demostrar por inducción que:

2 + 4 + ... + 2(n) = n(n + 1)

Demostración: Nuestra n-ésima proposición p(n) es:

2 + 4 + ... + 2(n) = n(n + 1)

y notese que:
p(1) = 2 = 1(2), donde 2 = 2
p(2) = 2 + 4 = 2(3), donde 6 = 6
p(3) = 2 + 4 + 6 = 3(4), donde 12 = 12
p(4) = 2 + 4 + 6+ 8 = 4(5), donde 20 = 20
.
.
.

Así p(1) asegura 2= 1( 1 + 1) y como es verdadera por inspección tal como lo establece la base de la inducción matemática.

Para el paso inductivo, supongamos que p(n) es verdadera para algún n, esto es

2 + 4 + ... + 2(n) = n(n + 1)

es verdadera. Ahora queremos probar que para p(n + 1)

2 + 4 + ... + 2(n) + (2(n + 1) = (n + 1)((n + 1) + 1)

es decir

2 + 4 + ... + 2(n) + (2n + 2) = (n + 1)(n + 2)

tal como lo establece el paso inductivo.


Como p(n) es verdadera por hipótesis, y trabajando con el lado izquierdo de la igualdad, temos que:

2 + 4 + ... + 2(n) + (2n + 2)

= [2 + 4 + ... + 2n] + (2n +2)
  = n(n + 1) + (2n + 2)
  = n(n + 1) + 2(n + 1)
  = (n + 1)(n + 2)


Entonces p(n + 1) es verdadera siempre que p(n) lo sea. Por el primer principio de inducción matemática se concluye que p(n) es verdadera n +.