Inducción matemática

Una descripción informal de la inducción matemática puede ser ilustrada por el efecto dominó, donde ocurre una reacción en cadena con una secuencia de piezas de dominó cayendo una detrás de la otra.

En matemáticas, la inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro $n\,$ que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

Premisa mayor: El número entero $a\,$ tiene la propiedad $P\,$.

Premisa menor: El hecho de que cualquier número entero $n\,$ tenga la propiedad $P\,$ implica que $n+1\,$ también la tiene (que se anota $n \Rightarrow n + 1$).

Conclusión: Todos los números enteros a partir de $a\,$ tienen la propiedad $P\,$.

Con más rigor, el método de inducción matemática es el que realiza la demostración para proposiciones en las que aparece como variable un número natural. Se basa en un axioma denominado principio de la inducción matemática.

Demostraciones por inducción

El razonamiento para demostrar una proposición cualquiera mediante el esquema del razonamiento es como sigue. Llamemos $P_n\,$ a la proposición, donde $n\,$ es el rango.

• Se demuestra que $P_0\,$, el primer valor que cumple la proposición (iniciación de la inducción), es cierta.
• Se demuestra que si se asume $P_n\,$ como cierta y como hipótesis inductiva, entonces $P_{n+1}\,$ lo es también, y esto sin condición sobre el entero natural $n\,$ (relación de inducción).

Luego, demostrado esto, concluimos por inducción, que $P_n\,$ es cierto para todo natural $n\,$.

La inducción puede empezar por otro término que $P_0\,$, digamos por $P_{n_0}\,$. Entonces $P_n\,$ será válido a partir del número $n_0\,$, es decir, para todo natural $n \ge n_0\,$.

Ejemplo 1

Para todo $n \ge 1$, $6^n\,$ es un número que acaba en 6.

Sea $P_n\,$ la proposición: «$6^n\,$ acaba en 6».

• Es claro que $P_1\,$ es cierto, porque $6^1 = 6\,$.

• Supongamos que $P_n\,$ es cierto para un valor de $n\,$ natural, y probemos $P_{n+1}\,$.

Un entero acaba por 6 si se puede escribir así: $10a+6\,$, con $a\,$ entero positivo o igual a cero. La hipótesis es, pues, $6^n=10a+6\,$.

Entonces $6^{n+1}=6(10a+6)=60a+36=60a+30+6=10(6a+3)+6=10c+6\,$, con $c=6a+3\,$, entero.

Esta última escritura prueba que $6^{n+1}\,$ acaba por 6, o sea que $P_{n+1}\,$ es cierto.

Luego $P_n\,$ es cierto para todo $n \ge 1\,$.

La inducción es válida por la construcción misma del conjunto de los naturales mediante los axiomas de Peano. En este caso:

• 1 es un natural;
• si $n\,$ lo es, entonces $n+1\,$ (sucesor de $n\,$) lo es también.

Existen otras inducciones, para otros conjuntos elaborados de forma distinta, como por ejemplo la inducción transfinita, y la inducción sobre las fórmulas de la lógica proposicional.

Además de la demostración por inducción, existe la definición o construcción por inducción. Por ejemplo, una sucesión aritmética puede ser definida como función de $n\,$: $u_n = a + rn\,$, o por inducción:

• $u_0 = a\,$
• $u_{n+1} = u_n + r\,$.

Ejemplo 2

Véase también: Sumatorio.

Se tratara de demostrar por inducción la siguiente proposición:

$\sum_{k=1}^n (2k - 1) 3^k = (n - 1) 3^{n+1} + 3$ $\forall n \in \mathbb{N}$

1. Se comprueba para n=1

$\sum_{k=1}^1 (2 - 1) 3^1 = 3 = (1 - 1) 3^{1+1} + 3$

Se tiene por tanto que la proposición es verdadera para n=1

2. Hipótesis inductiva (n=h)

$\sum_{k=1}^h (2k - 1) 3^k = (h - 1) 3^{h+1} + 3$

3. Tesis inductiva (n=h+1)

$\sum_{k=1}^{h+1} (2k - 1) 3^k = (h + 1 - 1) 3^{h+1+1} + 3$

$\sum_{k=1}^{h+1} (2k - 1) 3^k = h 3^{h+2} + 3$

4. Demostración de la tesis en base a la hipótesis

$\sum_{k=1}^{h+1} (2k - 1) 3^k = \sum_{k=1}^{h} (2k - 1) 3^k +(2(h+1) - 1) 3^{h+1}$

Se aplica la hipótesis de inducción:

$\sum_{k=1}^{h+1} (2k - 1) 3^k = (h - 1) 3^{h+1} + 3 + [2(h+1) - 1] 3^{h+1}$

$\sum_{k=1}^{h+1} (2k - 1) 3^k = (h - 1) 3^{h+1} + 3 + (2h+2 - 1) 3^{h+1}$

$\sum_{k=1}^{h+1} (2k - 1) 3^k = 3^{h+1} (h - 1 + 2h + 1) + 3$ (sacando factor común)

$\sum_{k=1}^{h+1} (2k - 1) 3^k = 3^{h+1} 3h + 3$

$\sum_{k=1}^{h+1} (2k - 1) 3^k = h 3^{h+2} + 3$

Por lo tanto, por verificarse la proposición para n=1 y para n=k+1 siendo k cualquier número natural, la proposición se verifica $\forall n \in \mathbb {N}$

Definición por inducción matemática

Los términos de una función pueden darse de manera explícita, usando fórmulas como

$f(n) =n^3 - 5n$

O por descripciones como

"Sea t_n el peso de la n-esima arista del camino".

Los valores de una función también pueden definirse por medio de indicaciones que involucren valores conocidos o anteriores.

Se dice en este caso que una función se define mediante inducción matemática siempre que:

(B) algún conjunto finito de valores, generalmente el primero o los primeros, se especifiquen,

(R) los valores reatantes están definidos en base a valores previos de la función. Una fórmula que hace esto se denomina fórmula inductiva o relación inductiva

El requisito (B) provee la base o punto de partida de la definición . El resto de los valores se halla empleando la fórmula inductiva (R) repetidamente. Como la relación se presenta una y otra vez; es decir es recurrente, se puede denominar también fórmula recursiva.

Factorial de n

Se define la función FACT como

(B) $FACT(0) = 1,$

(R) $FACT(n + 1) = (n + 1) \cdot FACT (n)$ para n ∈ ℕ

Puede emplearse (R) para calcular FACT(1), luego FACT(2) FACT(3); etc; y rápidamente, se ve FACT(n) = n!.

La sucesión de Fibonacci

Se define de la sigiente manera:

(B) $FIB(0)=FIB(1) = 1$

(R) $FIB(n) = FIB(n - 1) + FIB(n -2)$ para n≥ 2 ; n ∈ ℕ.

Nótese que la fórmula recursiva no tiene sentido para n = 1 , por lo que FIB(1) tuvo ser definida en la base. Los once primeros términos de esta sucesión son

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

Utilidad

Las definiciones mediante el principio de inducción matemática o las fórmulas recursivas adquieren suma importancia en la matemática discreta y, obviamente, en los casos de programación computacional. El número e = 2.718282... , base de los logaritmos naturales, puede se definido recursivamente y calcular su valor, mediante ordenadores, con la aproximación deseada.

Véase también

• Recurrencia
• Número natural
• Paradoja del caballo

Enlaces externos

• Weisstein, Eric W. «Principle of Mathematical Induction» (en inglés). MathWorld. Wolfram Research.
• Inducción matemática en PlanetMath
• Números naturales, principio de inducción