Indución matemática

Unha descrición informal da indución matemática pode ser ilustrada polo efecto dominó, onde ocorre unha reacción en cadea cunha secuencia de pezas de dominó caendo unha detrás da outra.

En matemáticas, a indución é un razoamento que permite demostrar proposicións que dependen dunha variable $n\,$ que toma unha infinidade de valores enteiros. En termos simples, a indución matemática consiste no seguinte razoamento:

O número enteiro $a\,$ ten a propiedade $P\,$. O feito de que calquera número enteiro $n\,$ tamén teña a propiedade $P\,$ implica que $n+1\,$ tamén a ten. Entón todos os números enteiros a partir de $a\,$ teñen a propiedade $P\,$.

A demostración está baseada no axioma denominado principio da indución matemática.

Historia

No Parmenides, diálogo de Platón do 370 a.C, quizais se pode identificar un temperán exemplo dunha explicación implícita de proba indutiva. A máis antiga pegada da indución matemática pódese atopar na demostración de Bhaskara I que empregando o «método cíclico» proba a infinidade dos números primos.

Unha técnica oposta, contando regresivamente en lugar de ascendentemente, pódese atopar no paradoxo sorites, onde se argumenta que se 10.000.000 de grans de area forman unha morea e removendo un gran da morea este continúa a ser unha morea, entón, un só gran (incluso ningún gran de area) forma unha morea.

Unha demostración implícita da indución matemática para secuencias aritméticas foi introducida por Al-Karaji na obra Al-Fakhri escrita ao redor do 1000 d. C., empregado para probar o teorema binomial e propiedades do triángulo de Pascal.

Ningún destes antigos matemáticos explicitou a hipótese indutiva. Outro caso similar foi o de Francesco Maurlico no seu Arithmeticorom libri duo (1575), que empregou a técnica para probar que a suma dos $n$ primeiros enteiros impares é igual a $n^{2}$.

A primeira formulación explícita sobre o principio de indución foi establecida polo físico e matemático Blaise Pascal na súa obra Traité du triangle arithmétique (1665). Outro francés, Fermat, fixo amplo uso dun principio relacionado para unha demostración indirecta do infinito descendente. A hipótese indutiva foi tamén empregada polo suízo Jakob Bernoulli e a partir de entón foi máis coñecida.

O moderno tratamento de carácter rigoroso e sistemático chegou con George Boole, Augustus De Morgan, Charles Sanders Peirce, Giuseppe Peano e Richard Dedekind.

Demostracións por indución

Chamemos $P_{n}\,$ á proposición, onde $n\,$ é o rango.

• "Base": Demóstrase que $P_{1}\,$ é certa, é dicir, é o primeiro valor que cumpre a proposición (iniciación da indución).
• "Paso indutivo": Demóstrase que se $P_{n}\,$ é certa, é dicir, como hipótese indutiva, entón $P_{n+1}\,$ tamén o é, e isto sen condición sobre o enteiro natural $n\,$ (relación de indución). Indicado como $n\Rightarrow n+1$).

Logo, demostrado isto, conclúese por indución que $P_{n}\,$ é certo para todo natural $n\,$.

A indución pode comezar por outro termo que non sexa $P_{1}\,$, por exemplo $P_{n_{0}}\,$. Entón $P_{n}\,$ será válido a partir do número $n_{0}\,$, é dicir, para todo natural $n\geq n_{0}\,$.

Exemplo

Probarase que a seguinte declaración P(n), que se supón válida para todos os números naturais n.

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

P(n) dá unha fórmula para a suma dos números naturais menores ou iguais a n. A proba de que P(n) é verdadeira para todos os números naturais procede como segue:

• Base: Móstrase que é válida para n = 1.

con P(1) tense:

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

No lado esquerdo da ecuación, o único termo é 1, entón o seu valor é 1, mentres que no termo dereito, 1·(1 + 1)/2 = 1.

Ambos os lados son iguais, n = 1. Entón P(1) é verdadeira.

• Paso indutivo: Mostrar que se P(k) é verdadeira, entón P(k+1) é verdadeira. Como segue:

Asúmese que P(k) é verdadeira (para un valor non específico de k). Débese entón mostrar que P(k+1) é verdadeira:

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

empregando a hipótese de indución P(k) é verdadeira, o termo esquerdo pódese reescribir:

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

Desenvolvendo:

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

mostrando de feito que P(k+1) é verdadeira.

Posto que se realizaron os dous pasos da indución matemática tanto a base como o paso indutivo, a declaración P(n) cúmprese para todo número natural $n$ Q.E.D.

Exemplo 2

Tratarase de demostrar por indución a seguinte proposición:

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

1. Compróbase para n=1

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

Tense por tanto que a proposición é verdadeira para n=1

2. Hipótese indutiva (n=h)

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

3. Tese indutiva (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}=h3^{h+2}+3$

4. Demostración da tese con base á hipótese

$\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 a hipótese de indució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}=h3^{h+2}+3$

Polo tanto, verificándose a proposición para $n=1$ e para $n=k+1$ sendo $k$ calquera número natural, a proposición verifícase $\forall n\in \mathbb {N}$.

Véxase tamén

Outros artigos

• Recursividade
• Número natural
• Paradoxo do cabalo
• Axiomas de Peano

Ligazóns externas

• Weisstein, Eric W. «Principle of Mathematical Induction». (en inglés)
• Principle of finite induction (en inglés)
• Números naturales, principio de inducción