Inducción matemática

Inducción matemática
técnica de prueba ^(es)
well-founded induction ^(en)

Una descripción informal de la inducción matemática pue ser ilustrada pol efeutu apoderó, onde asocede una reacción en cadena con una secuencia de pieces de dominó cayendo una detrás de la otra.

En matemátiques, la inducción ye un razonamientu que dexa demostrar proposiciones que dependen d'una variable ${\displaystyle n\,}$ que toma una infinidá de valores enteros. En términos simples, la inducción matemática consiste nel siguiente razonamientu:

El númberu enteru ${\displaystyle a\,}$ tien la propiedá ${\displaystyle P\,}$. El fechu de que cualquier númberu enteru ${\displaystyle n\,}$ tamién tenga la propiedá ${\displaystyle P\,}$ implica que ${\displaystyle n+1\,}$ tamién la tien. Entós tolos númberos enteros a partir de ${\displaystyle a\,}$ tienen la propiedá ${\displaystyle P\,}$.

La demostración ta basada nel axoma denomináu principiu de la inducción matemática.^[1]

Historia

Nel Parmenides, de Platón del 370 a.C, quiciabes puede identificase un tempranu exemplu d'una esplicación implícita de prueba inductiva. La más antigua buelga de la inducción matemática puede atopase na demostración de Euclides nel s. iii e.C. sobre la infinitud de los númberos primos y na de Bhaskara I usando'l so métodu cíclicu».

Una téunica reversa, cuntando regresivamente en llugar de ascendentemente, puede atopase na paradoxa sorites, onde s'argumenta que si 1 000 000 de granos de sable formen un montón y removiendo un granu del montón al empar, este sigue siendo un montón, entós, hasta un solu granu (inclusive nengún granu de sable) formaría un montón.

Una demostración implícita de la inducción matemática para secuencies aritmétiques foi introducida por Al-Karaji na so obra Al-Fakhri escrita alredor de 1000 d. C., usáu pa probar el teorema del binomiu y les propiedaes del triángulu de Pascal.

Nengún d'estos antiguos matemáticos explicitó la hipótesis inductiva. Otru casu similar foi'l de Francesco Maurlico nel so Arithmeticorom libri duo (1575), qu'usó la téunica pa probar que la suma de los n primeros enteros impares ye igual a n al cuadráu.

La primer formulación esplícita sobre'l principiu d'inducción foi establecida pol filósofu y matemáticu Blaise Pascal na so obra Traité du triangle arithmétique (1665).^[2] Otru francés, Fermat, fai ampliu usu d'un principiu rellacionáu pa una demostración indireuta del descensu infinitu. La hipótesis inductiva foi tamién emplegada pol suizu Jakob Bernoulli y a partir d'entós foi más conocida.

El tratamientu de calter rigorosu y sistemáticu llega solo nel sieglu xix con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano y Richard Dedekind.

Demostración per inducción

Llamemos ${\displaystyle P_{n}\,}$ a la proposición, onde ${\displaystyle n\,}$ ye'l rangu.

• Base: Demuéstrase que ${\displaystyle P_{1}\,}$ ye cierta, esto ye'l primer valor que cumple la proposición (iniciación de la inducción).
• Pasu inductivu: Demuéstrase que, si ${\displaystyle P_{n}\,}$ ye cierta, esto ye, como hipótesis inductiva, entós ${\displaystyle P_{n+1}\,}$ ser tamién, y esto ensin condición sobre l'enteru natural ${\displaystyle n\,}$ (rellación d'inducción. Indicáu como ${\displaystyle n\Rightarrow n+1}$).

Depués, demostráu esto, concluyimos por inducción, que ${\displaystyle P_{n}\,}$ ye ciertu pa tou natural ${\displaystyle n\,}$.

La inducción puede empezar por otru términu que nun seya ${\displaystyle P_{1}\,}$, digamos por ${\displaystyle P_{n_{0}}\,}$. Entós ${\displaystyle P_{n}\,}$ va ser válidu a partir del númberu ${\displaystyle n_{0}\,}$, esto ye, pa tou natural ${\displaystyle n\geq n_{0}\,}$.

Exemplu

va probase que la siguiente declaración P (n), que se supón válida pa tolos númberos naturales n.

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

P (n) da una fórmula pa la suma de los númberos naturales menores o igual a n. La prueba de que P (n) ye verdadera pa tolos númberos naturales procede como sigue.

Base: Amuésase que ye válida pa n = 1.
con P(1) tiense:

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

Nel llau esquierdu de la ecuación, l'únicu términu ye 1, entós el so valor ye 1.

ente que'l términu derechu, 1·(1 + 1)/2 = 1. 

Dambos llaos son iguales, n = 1. Entós P(1) ye verdadera.

Pasu inductivu: Amosar que si P(k) ye verdadera, entós P(k + 1) ye verdadera. Como sigue:

Se asume que P(k) ye verdadera (pa un valor non específicu de k). Débese entós amosar que P(k + 1) ye verdadera:

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

usando la hipótesis d'inducción P(k) ye verdadera, el términu esquierdu puede reescribise:

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

Desenvolviendo:

${\displaystyle {\begin{aligned}{\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{aligned}}}$

amosando de fechu que P(k + 1) ye verdadera.

Puesto que se realizaron los dos pasos de la inducción matemática tantu la base como'l pasu inductivu, la declaración P ( n ) cumplir pa tou númberu natural ${\displaystyle n}$ Q.Y.D.

Exemplu 2

va tratar de demostrar por inducción la siguiente proposición:

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

1. Comprobar pa n=1

${\displaystyle \sum _{k=1}^{1}(2-1)3^{1}=3=(1-1)3^{1+1}+3}$

Tener por tanto que la proposición ye verdadera pa n=1

2. Hipótesis inductiva (n=h)

${\displaystyle \sum _{k=1}^{h}(2k-1)3^{k}=(h-1)3^{h+1}+3}$

3. Tesis inductiva (n=h+1)

${\displaystyle \sum _{k=1}^{h+1}(2k-1)3^{k}=(h+1-1)3^{h+1+1}+3}$

${\displaystyle \sum _{k=1}^{h+1}(2k-1)3^{k}=h3^{h+2}+3}$

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

${\displaystyle \sum _{k=1}^{h+1}(2k-1)3^{k}=\sum _{k=1}^{h}(2k-1)3^{k}+(2(h+1)-1)3^{h+1}}$

Aplícase la hipótesis d'inducción:

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

${\displaystyle \sum _{k=1}^{h+1}(2k-1)3^{k}=(h-1)3^{h+1}+3+(2h+2-1)3^{h+1}}$

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

${\displaystyle \sum _{k=1}^{h+1}(2k-1)3^{k}=3^{h+1}3h+3}$

${\displaystyle \sum _{k=1}^{h+1}(2k-1)3^{k}=h3^{h+2}+3}$

Poro, verificándose la proposición pa ${\displaystyle n=1}$ y pa ${\displaystyle n=k+1}$ siendo ${\displaystyle k}$ cualquier númberu natural, la proposición verifícase ${\displaystyle \forall n\in \mathbb {N} }$.

La propiedá del bon orde

La validez de la inducción matemática ta basada nel principiu de bona ordenación de los conxuntos de númberos enteros non negativos.

Tou conxuntu d'enteros non negativos tien un elementu mínimu.

De cutiu utilízase esta propiedá direutamente nes demostraciones. ^[3]

Exemplu

Usa la propiedá del bon orde pa demostrar el algoritmu de la división, recuerda que l'algoritmu de la división diz que si a ye un númberu enteru y d ye un enteru positivu, entós hai dos únicos enteros c y r tales que 0${\displaystyle \leq }$r${\displaystyle \leq }$d y a=dc+r.

Solución: Sía S el conxuntu de los enteros non negativos de la forma a-dc, onde c ye un enteru. Esti conxuntu nun ye vacíu, porque como vemos -dc puede engrandase tanto como queramos, eso si, tomando c como un númberu enteru que nun seya negativu con un valor absolutu que seya grande, pola propiedá del bon orde, S tien mínimu un elementu r=a-dc₀.

L'enteru r nun puede ser negativu, tamién imaxinamos que r${\displaystyle \leq }$d, de nun ser asina, habría un númberu que nun sería negativu menor en S. Poro, esisten los enteros c y r', 0${\displaystyle \leq }$r${\displaystyle \leq }$d.

Referencies

1. "Diccionariu de Matemátiques" de Christopher Clapham (1998) ISBN 84-89784-56-6
2. Lokenath Debnath (2009), The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientifi
3. "Matemática discreta y les sos aplicaciones" Kenneth H. Rosen

Ver tamién

• Recurrencia
• Númberu natural
• Paradoxa del caballu
• Axomes de Peano

Enllaces esternos

• Weisstein, Eric W. «Principle of Mathematical Induction» (inglés). MathWorld. Wolfram Research.
• Númberos naturales, principiu d'inducción (enllaz rotu disponible n'Internet Archive; ver l'historial y la última versión).