Principio de inducción
Principio de inducción

El Principio de Inducción

Son famosas las construcciones con fichas de dominó en las que un pequeño golpe a la primera hace caer a todas ellas. Al acabar de estudiar lo que viene a continuación, se entenderá por qué este ejemplo ilustra con frecuencia lo que significa el principio de inducción.

Qué dice

Este principio afirma: " si  p es una propiedad definida sobre el conjunto ℕ  de los números naturales y se verifica:
1. p(0)          2. p(n) ⇒  p(n+1)   
entonces p es cierta para todo número natural "

Esquema                        Otras versiones

Cómo se aplica

Probar una propiedad p sobre ℕ  aplicando el Principio de Inducción, consiste en probar que para p se verifican los puntos 1. y 2. anteriores (de alguna de las versiones).

Los siguientes ejemplos, de carácter diverso, muestran este método y ponen de manifiesto la gran importancia que este principio puede llegar a alcanzar en matemática discreta.

Ejemplo: Suma de números impares

ENUNCIADO

Probar la igualdad:
1 + 3 + 5 + 7 + ... + (2n+1) = (n+1)2      ∀ n ∈ ℕ

SOLUCIÓN POR INDUCCIÓN

  • Cada número impar se describe como 2n+1. Para obtener el 1, n=0. En cuyo caso: 1 = (0 + 1)2.
  • Supongamos que 1 + 3 + ... + (2n-1) = n2.
    Veamos que esto permite probar que la fórmula es cierta para el caso siguiente:
    1 + 3 + ... + (2n-1) + (2n+1) = n2 + (2n+1) = (n+1)2

    		•

    PRUEBA VISUAL:          ..... para n=7

    Más ejemplos

    Con n rectas del plano en posición general ¿qué número Rn de regiones se producen en el plano?
                                               

    Probar que
    ( n 0 ) + ( n 1 ) + ( n 2 ) + ⋯ ⋯ +( n n−1 ) +( n n ) = 2​   n
    para todo número número natural n.       

    Se colocan n2 monedas formando un cuadrado nxn . Se trata de saber si desde cualquier moneda es posible realizar un itinerario que recorra todas las monedas pasando de una a otra contigua y sin cruzar dos veces por la misma.

          

    Carmen y Pedro invitan a su casa a n parejas. Antes de que alguien abandone la fiesta, Pedro pregunta por el número de personas a las que ha saludado cada uno. Las respuestas son todas diferentes. ¿Cuántas personas han saludado al anfitrión?