Se
é definida por
prove que:
Passo 1
O enunciado dá a sequência
definida por:
O que se pede: provar que, para todo
,
Passo 2
Estratégia que vamos usar (explicação didática): resolver recorrências lineares de ordem 2 com coeficientes constantes. A ideia-padrão é procurar soluções da forma
. Por que isso funciona? Porque, se substituirmos
na recorrência linear homogênea, obtemos uma equação algébrica em
(a equação característica) cuja solução nos dá os “modos” que compõem a solução geral. Se as raízes da equação característica são distintas, a solução geral é combinação linear desses modos.
Passo 3
Procurar soluções da forma
. Substituindo na recorrência:
Dividindo por
(não consideramos aqui
porque não produziria a família completa de soluções úteis), obtemos a equação característica:
Fatorando:
portanto as raízes são
e
, distintas.
Como as raízes são distintas, a solução geral da recorrência tem a forma
onde
e
são constantes a determinar pelas condições iniciais.
Passo 4
Aplicar as condições iniciais para achar
e
.
Para
:
Para
:
Subtraindo as duas equações:
Então
.
Portanto a solução particular fica
Passo 5
Agora fazemos uma prova por indução (ou forte indução) para garantir que a fórmula vale para todo
.
Base da indução:
As bases são verdadeiras.
Passo indutivo (indução forte): suponha que para algum
a fórmula valha para
e
, ou seja,
Usando a recorrência,
Desenvolvendo:
Simplificando potências de dois (note que
):
E
. Logo
Assim a fórmula vale para
. Pelo princípio da indução forte, a fórmula vale para todo
.
Passo 6
Conclusão: a fórmula encontrada satisfaz a equação característica, as condições iniciais e a recorrência por indução, portanto está provada.