Inducción matemática

De Wikipedia, la enciclopedia libre
(Redirigido desde «Demostración por Inducción»)
Saltar a: navegación, búsqueda
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 proposiciones que dependen de una variable n\, que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

El número entero a\, tiene la propiedad P\,. El hecho de que cualquier número entero n\, también tenga la propiedad P\, implica que n+1\, también la tiene. Entonces todos los números enteros a partir de a\, tienen la propiedad P\,.

La demostración está basada en el axioma denominado principio de la inducción matemática.[1]

Historia[editar]

En el Parmenides, diálogo de Platón del 370 a.C, quizá se puede identificar un temprano ejemplo de una explicación implícita de prueba inductiva. La más antigua huella de la inducción matemática se puede encontrar en la demostración de Bhaskara I que usando el «método cíclico» prueba la infinidad de los números primos.

Una técnica opuesta, contando regresivamente en lugar de ascendentemente, se puede encontrar en la paradoja sorites, en donde se argumenta que si 1.000.000 de granos de arena forman un montón y removiendo un grano del montón este sigue siendo un montón, entonces, un solo grano (incluso ningún grano de arena) forma un montón.

Una implícita demostración de la inducción matemática para secuencias aritméticas fue introducida por Al-Karaji en la obra Al-Fakhri escrita alrededor del 1000 d.C, usado para probar el teorema binomial y propiedades del triángulo de Pascal.

Ninguno de estos antiguos matemáticos explicitó la hipótesis inductiva. Otra caso similar fue el de Francesco Maurlico en su Arithmeticorom libri duo (1575), que usó la técnica para probar que la suma de los n primeros enteros impares es igual a n al cuadrado.

La primera formulación explícita sobre el principio de inducción fue establecida por el físico y matemático Blaise Pascal en su obra Traité du triangle arithmétique (1665).[2] Otro francés, Fermat, hace amplio uso de una principio relacionado para una demostración indirecta del infinito descendente. La hipótesis inductiva fue también empleada por el suizo Jakob Bernoulli, y a partir de entonces fue más conocida.

El moderno tratamiento de carácter riguroso y sistemático llega sólo en el siglo xix con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano y Richard Dedekind.

Demostraciones por inducción[editar]

Llamemos P_n\, a la proposición, donde n\, es el rango.

  • Base- Se demuestra que P_0\, es cierta, esto es el primer valor que cumple la proposición (iniciación de la inducción).
  • Paso inductivo- Se demuestra que si P_n\, es cierta, esto es, 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. Indicado como n \Rightarrow n + 1).

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 no sea 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[editar]

Se probará que la siguiente declaración P ( n ), que se supone válida para todos los números naturales n .

0 + 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\,.

P ( n ) da una fórmula para la suma de los números naturales menores o igual a n . La prueba de que P ( n ) es verdadera para todos los números naturales procede como sigue.

Base: Se muestra que es válida para n = 0.
con P(0) se tiene:

0 = \frac{0\cdot(0 + 1)}{2}\,.

En el lado izquierdo de la ecuación, el único término es 0, entonces su valor es 0.
mientras que el término derecho, 0·(0 + 1)/2 = 0.
Ambos lados son iguales, n = 0. Entonces P(0) es verdadera.

Paso inductivo: Mostrar que si P(k) es verdadera, entonces P(k + 1) es verdadera. Como sigue:

Se asume que P(k) es verdadera (para un valor no específico de k). Se debe entonces mostrar que P(k + 1) es verdadera:

(0 + 1 + 2 + \cdots + k )+ (k+1) = \frac{(k+1)((k+1) + 1)}{2}.

usando la hipótesis de inducción P(k) es verdadera, el término izquierdo se puede reescribir:

\frac{k(k + 1)}{2} + (k+1)\,.

Desarrollando:


\begin{align}
\frac{k(k + 1)}{2} + (k+1) & = \frac {k(k+1)+2(k+1)} 2 \\
& = \frac{k^2+k+2k+2}{2} \\
& = \frac{(k+1)(k+2)}{2} \\
& = \frac{(k+1)((k+1) + 1)}{2}
\end{align}

mostrando de hecho que P(k + 1) es verdadera.

Puesto que se han realizado los dos pasos de la inducción matemática tanto la base como el paso inductivo, la declaración P ( n ) se cumple para todo número natural n Q.E.D.

Ejemplo 2[editar]

Se tratará 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, verificándose 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}.

Referencias[editar]

  1. "Diccionario de Matemáticas" de Christopher Clapham (1998) ISBN: 84-89784-56-6
  2. Lokenath Debnath (2009), The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientifi

Véase también[editar]

Enlaces externos[editar]