FANDOM


O Princípio da Indução é um processo por meio do qual pode-se demonstrar a validade de proposições matemáticas que envolvem 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 $. No item (ii), a afirmação $ P(k) $ é chamada de hipótese de indução.

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 Editar

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 - Desigualdade de Bernoulli Editar

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 Editar

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 (Cone Sul 1992) Editar

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úmeros 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 $.

Exemplo (OBM 2006 - 3ª Fase - Nível 2) Editar

Em um torneio de tênis de mesa (no qual nenhum jogo termina empatado), cada um dos $ n $ participantes jogou uma única vez contra cada um dos outros. Sabe-se que, para todo $ k>2 $, não existem $ k $ jogadores $ J_1,J_2,\dots,J_k $ tais que $ J_1 $ ganhou de $ J_2 $, $ J_2 $ ganhou de $ J_3 $, $ J_3 $ ganhou de $ J_4 $, ..., $ J_{k-1} $ ganhou de $ J_k $, $ J_k $ ganhou de $ J_1 $.

Prove que existe um jogador que ganhou de todos os outros e existe um jogador que perdeu de todos os outros.

Solução: Vamos usar indução em $ n $. Para ajudar a nossa escrita, escrevermos $ Y \rightarrow X $ para indicar que $ X $ ganhou de $ Y $.

  • $ n=3 $

Sejam $ A $, $ B $ e $ C $ os três jogadores. Podemos supor sem perda de generalidade que $ B \rightarrow A $. Analisemos as possibilidades para os resultados do jogo de $ B $ contra $ C $.

1º Caso: $ C\rightarrow B $

Quanto o fica o jogo entre $ A $ e $ C $ neste caso? Observe que não podemos ter $ A \rightarrow C $, pois aí não teríamos as condições do enunciado. Logo $ C \rightarrow A $. Aqui, $ A $ é o jogador que ganhou de todos e $ C $ o perdedor das duas partidas que jogou.

2º Caso: $ B\rightarrow C $

Neste caso, $ B $ é o perdedor. Já para encontrarmos o vencedor, basta tomarmos aquele que vencer a partida entre $ A $ e $ C $.

Portanto, a afirmação vale para o caso $ n=3 $.

  • Suponhamos que a afirmação do enunciado seja válida para $ n $ jogadores e provemos que ela vale para $ n+1 $.

Vamos nomear os jogadores aqui também: $ A_1,A_2,\dots,A_n,A_{n+1} $. Para podermos usar a hipótese de indução, consideremos apenas os jogos entre $ A_1,A_2,\dots,A_n $. Se usarmos-a, poderemos concluir que existe um jogador que vence todas essas partidas, que chamaremos, sem perda de generalidade, de $ A_1 $.

Ao acrescentarmos o jogador $ A_{n+1} $ que será o vencedor: $ A_1 $ ou $ A_{n+1} $. Para descobrirmos isso, precisamos analisar os possíveis resultados do jogo entre os dois.

1º Caso: $ A_{n+1} \rightarrow A_1 $

Neste caso, $ A_1 $ é o jogador que venceu todas as partidas.

2º Caso: $ A_1 \rightarrow A_{n+1} $

Nenhum dos jogadores $ A_2,\dots,A_n $ pode ser o ganhador, pois todos estes perderam de $ A_1 $. Será que $ A_{n+1} $ ganhou de todos esses? Observe que não podemos ter $ A_{n+1} \rightarrow A_2 $, pois isto implicaria $ A_1 \rightarrow A_{n+1} $, $ A_{n+1} \rightarrow A_2 $ e $ A_2 \rightarrow A_1 $, o que contradiz o enunciado. Logo, $ A_2 \rightarrow A_{n+1} $. Analogamente, $ A_3,\dots,A_n $ perderam de $ A_{n+1} $, o que torna este o vencedor.

Portanto, sempre existe um vencedor neste campeonato.

Exemplo (OBM 2011 - 3ª Fase - Nível 3) Editar

Para qualquer número natural $ N $ de $ 2k $ dígitos, seja $ I(N) $ o número de $ k $ dígitos obtido escrevendo os algarismos de ordem ímpar de $ N $ da esquerda para a direita e $ P(N) $ como o número de $ k $ dígitos obtido escrevendo os algarismos de ordem par de $ N $ da esquerda para direita. Por exemplo, $ I(249035)=405 $ e $ P(249035)=293 $. Provar que não é possível encontrar um natural $ N $ de $ 2k $ algarismos tal que $ N=I(N).P(N) $.

Solução: Vamos usar indução em $ k $.

  • $ k=1 $

Aqui $ N $ tem $ 2 $ algarismos e por isso podemos escrever $ N=\overline{ab}=10a+b $.

Provaremos que $ N>I(N).P(N)(*) $. Para isto, reescreveremos esta expressão de modo equivalente. Observe que

$ N>I(N).P(N) \Leftrightarrow 10a+b>ab \Leftrightarrow a(10-b)+b>0 $.

Observe que $ a>0 $ (ele não pode ser igual a zero, pois se ele fosse, $ N $ teria apenas um algarismo). Além disso, $ 0 \leq b <10 $, de onde segue que a desigualdade é verdadeira.

  • Suponha que $ (*) $ seja válido para todo $ N' $ com $ 2(k-1) $ dígitos. Provaremos que vale também para os números de $ 2k $ dígitos.

Com efeito, vamos montar o número com $ 2k $ algarismos a partir de $ N' $. Para isso, vamos adicionar os algarismos $ x $ e $ y $ à esquerda de $ N' $ e formar $ N=\overline{xyN'}=10^{2k-1}x+10^{2k-2}y+N' $.

Queremos mostrar que $ N>I(N).P(N) $. Para facilitar a nossa escrita, vamos escrever

$ \varepsilon=P(N') $

$ \theta=I(N') $.

Observe que $ \varepsilon $ e $ \theta $ possuem $ k-1 $ dígitos cada e por hipótese de indução $ N'>\theta \varepsilon $. Além disso, podemos calcular $ I(N) $ e $ P(N) $ em função do que já temos.

$ P(N)=\overline{x\varepsilon}=x.10^{k-1}+\varepsilon $

$ I(N)=\overline{y\theta}=y.10^{k-1}+\theta $.

Vamos reescrever o que queremos provar de um modo equivalente:

$ N>I(N).P(N)\Leftrightarrow $

$ \Leftrightarrow 10^{2k-1}x+10^{2k-2}y+N'>(x.10^{k-1}+\varepsilon)(y.10^{k-1}+\theta)\Leftrightarrow $

$ \Leftrightarrow 10^{2k-1}x+10^{2k-2}y+N'>10^{2k-2}xy+10^{k-1}(x\theta+y\varepsilon)+\varepsilon \theta (**) $.

Já sabemos pela hipótese de indução que $ N'>\theta \varepsilon $. Assim, para mostrarmos $ (**) $, basta provarmos que

$ 10^{2k-1}x+10^{2k-2}y>10^{2k-2}xy+10^{k-1}(x\theta+y\varepsilon) $.

Vamos continuar procurando uma desigualdade equivalente a essa. Se dividirmos ambos os lados por $ 10^{k-1} $:

$ 10^{k}x+10^{k-1}y>10^{k-1}xy+(x\theta+y\varepsilon) (***) $.

Como podemos provar isto? Observe que $ \varepsilon $ e $ \theta $ possuem $ k-1 $ algarismos e por isso são menores ou iguais a $ 10^{k-1}-1 $. Com isso, conseguimos fazer aparecer $ x\theta+y\varepsilon $ em uma desigualdade:

$ x\theta+y\varepsilon \leq x(10^{k-1}-1)+y(10^{k-1}-1)=(10^{k-1}-1)(x+y) $.

Vamos forçar o lado direito de $ (***) $ aparecer. Para isto, somaremos $ 10^{k-1}xy $ em ambos os lados da desigualdade anterior:

$ x\theta+y\varepsilon+10^{k-1}xy \leq 10^{k-1}xy+(10^{k-1}-1)(x+y) $.

Se mostrarmos que

$ 10^{k-1}xy+(10^{k-1}-1)(x+y)<10^{k}x+10^{k-1}y $,

então $ (***) $ fica demonstrada. A desigualdade acima equivale a

$ 10^{k-1}xy+10^{k-1}x<10^kx+x+y $.

Observe que

$ 10^{k-1}xy+10^{k-1}x=10^{k-1}x(y+1) \leq 10^{k-1}x.10=10^kx<10^kx+x+y. $

Isto prova $ (***) $ e portanto a afirmação do enunciado é verdadeira.

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 $.