Exercício 1.23. Considere a sequência numérica ( o_{n} ) definida recursivamente por a_{0}=2, a_{1}=5, e para todo n \geq 2, a_{n}=5 a_{n-1}-6 a_{n-2}. Demonstre, utilizando o indução forte, que
a_{n}=2^{n}+3^{n} \quad \text { para todo } n \geq 0 .

Passo 1

O enunciado fornece uma sequência (a_n) definida por recorrência e pede para provar, por indução forte, a fórmula fechada
a_{n}=2^{n}+3^{n}\quad\text{para todo }n\ge 0.
Informações dadas:
  • a_{0}=2.
  • a_{1}=5.
  • Para todo n\ge 2,
a_{n}=5a_{n-1}-6a_{n-2}.
O que se pede: demonstrar que a fórmula \;a_{n}=2^{n}+3^{n}\; vale para todo n\ge0, usando indução forte.

Passo 2

Breve explicação do método que vou usar (indução forte), porque o enunciado pede isso e porque é natural aqui.
Indução forte é uma forma de prova por indução em que, para provar a propriedade para um certo n, assumimos que a propriedade já é verdadeira para todos os índices menores que n (não apenas para o caso n-1 como na indução simples). Em símbolos: para mostrar que P(n) vale para todo n\ge0, procede-se assim:
  • Verificar casos base (normalmente vários, conforme necessário).
  • Mostrar que, para qualquer n\ge algum valor (a partir de onde começamos o passo indutivo), se P(k) é verdadeira para todo k com 0\le k\le n-1, então P(n) também é verdadeira.
Aqui a recorrência usa a_{n-1} e a_{n-2}, por isso precisamos das bases n=0 e n=1; com isso, ao assumir verdade para todos os k\le n-1 poderemos substituir a_{n-1} e a_{n-2} pelas suas formas fechadas.

Passo 3

Verificação do caso base n=0.
A fórmula proposta dá, para n=0,
2^{0}+3^{0}=1+1=2.
Como o enunciado dá a_{0}=2, temos que a fórmula coincide com a_{0}. Portanto P(0) é verdadeira.

Passo 4

Verificação do caso base n=1.
A fórmula proposta dá, para n=1,
2^{1}+3^{1}=2+3=5.
Como o enunciado dá a_{1}=5, a fórmula coincide com a_{1}. Portanto P(1) é verdadeira.

Passo 5

Passo indutivo (indução forte).
Seja n\ge 2. Suponha, como hipótese de indução forte, que para todo inteiro k com 0\le k\le n-1 vale
a_{k}=2^{k}+3^{k}.
Em particular, essa hipótese nos dá as expressões para a_{n-1} e a_{n-2}, que são justamente as que precisamos na recorrência.

Passo 6

Usar a recorrência e a hipótese de indução para calcular a_{n}.
Começamos pela recorrência dada:
a_{n}=5a_{n-1}-6a_{n-2}.
Aplicando a hipótese de indução (substituindo a_{n-1}=2^{n-1}+3^{n-1} e a_{n-2}=2^{n-2}+3^{n-2}), obtemos
a_{n}=5\bigl(2^{n-1}+3^{n-1}\bigr)-6\bigl(2^{n-2}+3^{n-2}\bigr).
Agora desenvolvo separadamente as partes que envolvem potências de 2 e de 3.
Para as potências de 2:
5\cdot 2^{n-1}-6\cdot 2^{n-2} =2^{n-2}\bigl(5\cdot 2 -6\bigr) =2^{n-2}\bigl(10-6\bigr) =2^{n-2}\cdot 4 =2^{n}.
Aqui usei que 2^{n-1}=2\cdot 2^{n-2}, fatorando 2^{n-2}.
Para as potências de 3:
5\cdot 3^{n-1}-6\cdot 3^{n-2} =3^{n-2}\bigl(5\cdot 3 -6\bigr) =3^{n-2}\bigl(15-6\bigr) =3^{n-2}\cdot 9 =3^{n}.
Aqui usei que 3^{n-1}=3\cdot 3^{n-2}, fatorando 3^{n-2}.
Somando as duas partes:
a_{n}=2^{n}+3^{n}.
Portanto, sob a hipótese de indução forte, mostramos que P(n) é verdadeira.

Passo 7

Conclusão final da indução.
Tendo verificado os casos base n=0 e n=1 e mostrado que, para todo n\ge 2, a validade da propriedade para todos os k\le n-1 implica sua validade para n, pela princípio da indução forte concluímos que
a_{n}=2^{n}+3^{n}\quad\text{para todo }n\ge 0.

Resposta

\displaystyle a_{n}=2^{n}+3^{n}

Exercícios relacionados