FANDOM


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. Ele é equivalente ao Princípio da Boa Ordenação .

Como provar que alguma propriedade vale para todo número natural?Editar

Existem coisas que você quer provar que valem para todo número natural. Por exemplo,

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

Você pode até pensar: vamos verificar que a igualdade é válida para alguns valores: n=1,2,3 etc. Se você fizer isso, perceberá que funciona: a igualdade é válida para estes números. Mas afinal, ela vale para todo n natural? Ora, verificar algo para vários valores não é uma prova? NÃO. Veja os seguintes exemplos:

ExemploEditar

É verdade que a expressão n^4-10x^3+35x^2-50x+24 é igual a zero para todo n natural?

Solução:

Vejamos esta expressão para alguns valores de n:

  • n=1

1^4-10.1^3+35.1^2-50.1+24=1-10+35-50+24=0.

  • n=2

2^4-10.2^3+35.2^2-50.2+24=16-80+140-100+24=0.

  • n=3

3^4-10.3^3+35.3^2-50.3+24=81-270+315-150+24=0.

  • n=4

4^4-10.4^3+35.4^2-50.4+24=256-640+560-200+24=0.

A afirmação é verdadeira para n=1,2,3 e 4. Podemos dizer que ela vale sempre? NÃO. Ela não vale para n=5:

5^4-10.5^3+35.5^2-50.5+24=625-1250+825-250+24=-26.

Exemplo (Polinômio de Euler)Editar

Para todo n natural, f(n)=n^2-n+41 é um número primo.

Solução:

Se você fizer n=0,1,2,3,...,40 irá obter somente números primos. Mas

f(41)=41^2-41+41=41^2

que não é um número primo.

Princípio da Indução FinitaEditar

Seja P(n) uma propriedade dos números naturais. O Princípio da Indução Finita (ou Princípio da Indução Matemática) estabelece que: se as afirmações

(i) "P(1) é válida"

(ii) "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\ge1.

Usando o PIFEditar

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çõesEditar

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\ge1+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\cdot1\ge1+r\cdot1 (o que, de fato, está certo). Supondo ser verdadeiro para n=k, temos que (1+r)^k\ge1+rk. Para n=k+1, segue que (1+r)^{k+1}=(1+r)^k\cdot(1+r)\ge(1+rk)(1+r)=1+r+rk+r^2k=1+r(k+1)+r^2k>1+r(k+1), logo (1+r)^{k+1}\ge1+r(k+1). Portanto, é válido que (1+r)^n\ge1+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.

Exemplo 4 (Cone Sul)

Considere o conjunto S de 100 números: 1, \frac{1}{2}, \frac{1}{3},..., \frac{1}{100}. Quaisquer dois números, a e b, são eliminados em S, e o número a+b+ab é adicionado. Agora, existem 99 números em S. Depois de fazermos esta operação 99 vezes, existe apenas 1 número em S. Quais valores este número pode ter?

Solução:

Vamos começar com casos particulares para entendermos melhor o problema.Para nos ajudar, vamos considerar a operação * definida por x*y=x+y+xy. Essa operação tem algo interessante: x*y=y*x, para quaisquer x e y reais (o que chamamos de propriedade comutativa da operação).

Se começarmos com 2 núumeros, digamos a e b, terminaremos com o número a*b.

Já se começarmos com a, b e c, existem três possibilidades para o número final: (a*b)*c, (b*c)*a e (c*a)*b. Aqui acontece uma coisa interessante: os três números são iguais. Coincidência? Não! De fato, para quaisquer x,y e z reais vale o seguinte: (x*y)*z=x*(y*z) (isto é o que chamamos de propriedade associativa). Desta forma, se começarmos com a, b e c, terminaremos com a*b*c.

E se os núumeros do começo forem a, b, c e d? Se combinarmos as propriedades comutativa e associativa, veremos que a única possibilidade para o último número será a*b*c*d. O mesmo vale para qualquer quantidade de termos iniciais.

Desta forma, o número final do problema será

1*\frac{1}{2}*\frac{1}{3}*...*\frac{1}{100}.

Com isso, para terminarmos o problema precisamos calcular este valor. Façamos alguns casos particulares.

  • n=1

1=1

  • n=2

1*\frac{1}{2}=1+\frac{1}{2}+1.\frac{1}{2}=2

  • n=3

1*\frac{1}{2}*\frac{1}{3}=(1*\frac{1}{2})*\frac{1}{3}=2*\frac{1}{3}=2+\frac{1}{3}+2.\frac{1}{3}=3.

Podemos suspeitar que

1*\frac{1}{2}*\frac{1}{3}*...*\frac{1}{n}=n.

Será? Lembre-se: fazer alguns exemplos não prova nada! Vamos usar indução em n para provar este resultado. Já provamos que esta afirmação vale para n=1. Suponha que ela seja válida para n=k, ou seja,

1*\frac{1}{2}*\frac{1}{3}*...*\frac{1}{k}=k.

Provaremos que ela vale para n=k+1. Com efeito, 1*\frac{1}{2}*\frac{1}{3}*...*\frac{1}{k}*\frac{1}{k+1}=k*\frac{1}{k+1}=k+\frac{1}{k+1}+\frac{k}{k+1}=k+1.

Logo,

1*\frac{1}{2}*\frac{1}{3}*...*\frac{1}{n}=n.

Em particular,

1*\frac{1}{2}*\frac{1}{3}*...*\frac{1}{100}=100.

Ou seja, irá sobrar somente o número 100.

Caso Especial da InduçãoEditar

Seja P(n) uma propriedade dos números naturais. O Princípio da Indução Finita (ou Princípio da Indução Matemática) estabelece que: se as afirmações

(i) "P(n_0) é válida"

(ii) "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\ge n_0.

Indução ForteEditar

Se as afirmações

(i) "P(1) é válida"

(ii) "se P(1), P(2), \dots, 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\ge1.