FANDOM


O Princípio da Indução (ou Princípio da Indução Finita, também conhecido como PIF) é 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) (Base da Indução) $ P(1) $ é válida;

(ii) (Passo Indutivo) 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 $. 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.

Observação Editar

Se o enunciado lhe pedir para encontrar algo para um valor muito grande de $ n $, uma possível estratégia é verificar que aquilo é válido para todo $ n $ natural (usando indução) e depois particularizar para o valor do enunciado.

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

Em cada casa de um tabuleiro quadriculado $ 2000 \times 2000 $ deve-se escrever um dos três numeros: $ -1,0 $ ou $ 1 $. Se, em seguida, somam-se os números escritos em cada linha e cada coluna, obtêm-se $ 4000 $ resultados. Mostre que é possível preencher o tabuleiro de modo que os $ 4000 $ resultados assim obtidos sejam todos distintos.

Solução: Comecemos com pequenos casos: uma tabela $ 2\times 2 $.

ConeSul2001q1

A partir daí, vamos aproveitar este tabuleiro para preenchermos um que seja $ 4 \times 4 $.

Vamos manter iguais as somas da primeira e da segunda linhas e da primeira e segunda colunas. Como fazer isto? Basta colocarmos $ 1 $ e $ -1 $ em cada uma das fileiras.

ConeSul2001q11

Já temos as somas $ -1,0,1,2 $. Façamos aparecer $ -3,-2,3,4 $.

ConeSul2001q12

Podemos fazer isto de maneira mais geral: construiremos um tabuleiro $ (2k+2) \times (2k+2) $, que satisfaça as condições do enunciado, a partir de um tabuleiro $ 2k \times 2k $.

Suponhamos que o tabuleiro $ 2k \times 2k $ tenha somas de suas fileiras iguais a $ -(2k-1), -(2k-2),\dots,2k-2,2k-1,2k $. Coloque o tabuleiro $ 2k \times 2k $ no canto esquerdo superior.

Para que as somas das primeiras $ 2k $ e $ 2k $ colunas não mudem, colocaremos $ 1 $ e $ -1 $ para que as somas se cancelem. Mais precisamente, nas $ 2k $ primeiras casas da $ 2k+1 $-ésima linha e da $ 2k+1 $-ésima coluna, colocaremos $ 1 $'s. Já as $ 2k $ primeiras casas da $ 2k+2 $-ésima linha e da $ 2k+2 $-ésima coluna, colocaremos $ -1 $'s.

Nas fileiras que ainda não calculamos as somas, façamos aparecer $ -(2k+1),-2k,2k+1,2k+2 $. Para isto, façamos conforme a figura abaixo.

ConeSul2001q13

Assim, conseguimos todas as somas distintas (que irão variar de $ -(2k+1) $ a $ 2k+2 $). Portanto é possível preencher um tabuleiro $ 2n \times 2n $ conforme as condições do enunciado para todo $ n $. Em particular, podemos fazer isso para o tabuleiro $ 2000 \times 2000 $.

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

Quando devemos usar indução forte? Quando, no passo indutivo, não conseguimos provar $ P(n+1) $ apenas usando $ P(n) $ e sim usando $ P(n_0), P(n_0+1),P(n_0+2) \dots, P(n) $.

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) (Base da Indução) $ P(n_0) $ é válida;

(ii) (Passo Indutivo) 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(n_0) $ é válida;

(ii) Se $ P(n_0), P(n_0+1),P(n_0+2) \dots, P(n) $ são válida então $ P(n+1) $ também é válida.

são ambas verdadeiras, então $ P(n) $ é válida para qualquer $ n\geq n_0 $.

Exemplo (Cone Sul 2003) Editar

Considere a sequência $ \{a_n\} $ definida da seguinte maneira:

$ a_1=1 $

$ a_2=3 $

$ a_{n+2}=2a_{n+1}a_n+1 $, para todo inteiro $ n \geq 1 $.

Provar que a máxima potência de $ 2 $ que divide $ a_{4006}-a_{4005} $ é $ 2^{2003} $.

Solução: Façamos alguns casos particulares.

$ a_3=2a_2a_1+1=2.1.3+1=7 $

$ a_4=2a_3a_2+1=2.7.3+1=43 $

$ a_5=2a_4a_3+1=2.43.7+1=603 $

Para nos ajudar aqui, defina

$ A_n=a_n-a_{n-1}, $

para $ n \geq 2 $ natural. Com isso,

$ A_2=a_2-a_1=3-1=2 $

$ A_3=a_3-a_2=7-3=4 $

$ A_4=a_4-a_3=43-7=36 $

$ A_5=a_5-a_4=603-43=560. $

Estes casos particulares nos fazem suspeitar que a maior potência que $ A_{2n} $ é $ 2^n $ e que $ 2^{n+1} \mid A_{2n+1} $. Vamos usar indução forte em $ n $ para mostrarmos estas duas afirmações ao mesmo tempo. Observe que se mostrarmos apenas a primeira afirmação, resolveremos o problema. Mas precisaremos da segunda afirmação para mostrarmos a primeira.

(i) Já fizemos os casos $ n=1 $ e $ n=2 $.

(ii) Suponha que ambas as afirmações que queríamos mostrar sejam verdadeiras para todos os valores menores ou iguais a $ n $. Provaremos que elas também são válidas também para $ n+1 $.

Observe que

$ A_{2(n+1)}=A_{2n+2}=a_{2n+2}-a_{2n+1}=2a_{2n+1}a_{2n}+1-(2a_{2n}a_{2n-1}+1)=2a_{2n}(a_{2n+1}-a_{2n-1}). $

Para podermos usar a hipótese, precisamos fazer $ A_{2n} $ aparecer. Para isso, façamos

$ A_{2(n+1)}=2a_{2n}(a_{2n+1}-a_{2n}+a_{2n}-a_{2n-1})=2a_{2n}(A_{2n+1}+A_{2n}). $

Por hipótese de indução, existe $ x_{2n} $ ímpar tal que $ A_{2n}=2^nx_{2n} $ e $ x_{2n+1} $ inteiro tal que $ A_{2n+1}=2^{n+1}x_{2n+1}(*) $. Com isso,

$ A_{2(n+1)}=2a_{2n}(2^{n+1}x_{2n+1}+2^nx_{2n})=2^{n+1}a_{2n}(2x_{2n+1}+x_{2n}).(**) $

Podemos afirmar que $ a_{2n}(2x_{2n+1}+x_{2n}) $ é ímpar? Note que $ 2x_{2n+1}+x_{2n} $ é ímpar, pois $ x_{2n} $ também é. E quanto a $ a_{2n} $? Podemos ver que é ímpar pela definição da sequência $ \{a_n\} $.

Desta forma, a maior potência de $ 2 $ que divide $ A_{2(n+1)} $ é $ 2^{n+1} $.

Vejamos agora que $ 2^{(n+1)+1} \mid A_{2(n+1)+1} $. De fato, de modo análogo ao que fizemos anteriormente

$ A_{2(n+1)+1}=A_{2n+3}=2a_{2n+1}(A_{2n+2}+A_{2n+1}). $

Por $ (*) $ e $ (**) $,

$ A_{2n+3}=2a_{2n+1}(2^{n+1}a_{2n}(2x_{2n+1}+x_{2n})+2^{n+1}x_{2n+1})=2^{n+2}a_{2n+1}(a_{2n}(2x_{2n+1}+x_{2n})+x_{2n+1}). $

Desta forma, $ 2^{(n+1)+1} \mid A_{2(n+1)+1} $. Com isso, a maior potência de $ 2 $ que divide $ A_{4006}=a_{4006}-a{4005} $ é $ 2^{2003} $.