Suponha que os números an são definidos por indução por a1=1, a2=2, a3=3 e an=an-3-an-2-an-1 para todo n >= 4. Use o Segundo Princípio da Indução Finita para mostrar que an<2^n para todo inteiro positivo n.

Passo 1

Beleza, aqui o que a questão diz é: temos a sequência
a1=1, a2=2, a3=3
e, pra todo an=an-3-an-2-an-1,
an<2^n
O que pedem é usar o Segundo Princípio da Indução (indução forte) pra mostrar que

para todo .
Conteúdo que vamos usar:
1. Indução forte (supor a propriedade para todos os valores até ).
2. Desigualdade triangular e valor absoluto, para controlar o “menos” das subtrações.
3. Propriedade de soma de potências de 2.

Passo 2

Casos-base (verificar manualmente os primeiros ):
  • Para : e . Então .
  • Para : e . Então .
  • Para : e . Então .
    Pronto, a desigualdade vale para .

Passo 3

Hipótese de indução forte: suponha que para todo inteiro |am|<2^m com já temos
Repare que, ao controlar , automaticamente controlamos porque .

Passo 4

Vamos provar que então ak+1 = a(k+1)-3 ;-; a(k+1)-2 ;-; a(k+1)-1 = ak-2-ak-1-ak , o que implica |ak+1| =|,ak-2+(-ak-1)+(-ak)| ;<=;|ak-2| ;+;|ak-1| ;+;|ak| .
Usando a definição para |ak-2|<2^,k-2, |ak-1|<2^,k-1, |ak|<2^k :
|ak+1| < 2^k-2 + 2^k-1 + 2^k =2^k-2l(1+2+4r) =7cdot2^,k-2 =74,2^k
Agora aplicamos a desigualdade triangular em valor absoluto:
74,2^k <2cdot2^k=2^,k+1
Pela hipótese de indução forte, cada um desses três valores satisfaz
|ak+1|<2^,k+1 Longrightarrow ak+1<=|ak+1|<2^,k+1
Somando-as:
Como , temos
Logo
Isso conclui o passo de indução.

Resposta

Para todo inteiro positivo an<2^n, , vale
como queríamos demonstrar.

Exercícios relacionados