Princípio da Indução Finita

Indução matemática é um processo por meio do qual pode-se demonstrar a validade de uma proposição matemática nos números naturais.

Princípio da Indução Finita

Definição

Seja $P(n)$ uma propriedade dos números naturais. O Princípio da Indução Finita estabelece que: se as afirmações "$P(1)$ é válida" e "se $P(k)$ é válida então $P(k+1)$ também é válida" são ambas verdadeiras, então $P(n)$ é válida para qualquer $n \geq 1$.

Usando o PIF

A prova por indução consiste, basicamente, em três passos:

• demonstrar que a proposição é válida para um $n$ pequeno (geralmente se utiliza $n=1$, embora em alguns problemas pode não ser possível: nesse caso, o mais comum é utilizar o menor valor possível para $n$);
• supor que seja válido para qualquer $n=k$;
• a partir dessa suposição, demonstrar que, se a proposição vale para $n=k$, então também vale para $n=k+1$.

Veja que, se a afirmação for válida para $n=1$, e para $n=k+1$ caso seja para $n=k$, de fato será válida para todo número natural: se $n=k=1$ (caso em que já provamos a validade), então também será para $n=k+1=2$. Assim, por este processo, concluímos que a afirmação é válida para $n = 3$, $n = 4$, e assim por diante.

Exemplos e Aplicações

A demonstração por indução matemática pode ser aplicada em diversos problemas, principalmente os referentes a álgebra e aritmética:

Exemplo 1: Demonstre que a soma dos $n$ primeiros números ímpares é igual a $n^2$.

Solução: Resolveremos por indução matemática. Inicialmente, note que o n-ésimo número ímpar é igual a $2n-1$. Logo, a soma dos $n$ primeros números ímpares é $1+3+5+\cdots +(2n-1)$. Para $n=1$, temos que a soma é $1=1^2$, então a afirmação é válida. Supondo ser válido para $n=k$, segue que $1+3+5+\cdots +(2k-1)=k^{2}$. E, para $n=k+1$, a soma dos $n+1$ primeiros números ímpares é $1+3+5+\cdots +(2k-1)+(2k+1)$; como $1+3+5+\cdots +(2k-1)=k^{2}$, a soma dos $k+1$ primeiros números ímpares é $k^2+2k+1=(k+1)^2$. Assim, de fato, a soma dos $n$ primeiros números ímpares é igual a $n^2$.

Exemplo 2: Prove que $(1+r)^{n}\geq 1+r\cdot n$ para todo $r > 0$.

Solução: Por indução matemática, começamos por $n=1$, para o qual temos que $(1+r)^{1}=1+r\cdot 1\geq 1+r\cdot 1$ (o que, de fato, está certo). Supondo ser verdadeiro para $n=k$, temos que $(1+r)^{k}\geq 1+rk$. Para $n=k+1$, segue que $(1+r)^{k+1}=(1+r)^{k}\cdot (1+r)\geq (1+rk)(1+r)=1+r+rk+r^{2}k=1+r(k+1)+r^{2}k>1+r(k+1)$, logo $(1+r)^{k+1}\geq 1+r(k+1)$. Portanto, é válido que $(1+r)^{n}\geq 1+r\cdot n$ para todo $r > 0$.

Exemplo 3: Seja $n$ um inteiro positivo. Para cada um dos inteiros $n+1,n+2,\cdots ,2n$ considere o seu maior divisor ímpar. Prove que a soma de todos estes divisores é igual a $n^2$.

Solução: Inicialmente, vamos definir uma função $f$ tal que $f(n)$ seja o maior divisor ímpar de $n$. Para $n=1$, temos a soma $S_{1}=f(2)=1$ (veja que o maior divisor ímpar de $2$ é $1$). Supondo que a propriedade seja válida para $n=k$, temos que $f(k+1)+f(k+2)+\cdots +f(2k)=k^{2}$. Para $n=k+1$, temos $S_{k+1}=f(k+2)+f(k+3)+\cdots +f(2k)+f(2k+1)+f(2k+2)$; note que $2k+2=2(k+1)$, logo $f(2k+2)=f(k+1)$ (pois qualquer divisor ímpar de $2k+2$ está entre os divisores ímpares de $k+1$). E, como $2k+1$ é ímpar, $f(2k+1)=2k+1$. Assim, segue que $S_{k+1}=f(k+2)+f(k+3)+\cdots +f(2k)+[2k+1]+f(k+1)=k^{2}+2k+1=(k+1)^{2}$. Está, portanto, provado que a soma de todos os referidos divisores é igual a $n^2$.