09 Seja
a sequência de Fibonacci definida por
e
para todo inteiro não negativo
.
Mostre que, para todos os inteiros não negativos
,
Mostre que, para todos os inteiros não negativos
Passo 1
O enunciado trata da sequência de Fibonacci
definida por
Queremos mostrar, para quaisquer inteiros não negativos
e
, que
O método escolhido será a indução sobre
, mantendo
fixo.
Passo 2
Base da indução
.
No lado esquerdo temos
No lado esquerdo temos
No lado direito,
Logo, a fórmula vale para
.
Passo 3
Hipótese de indução.
Suponha que, para algum , valha
Suponha que, para algum
Queremos então provar que
Passo 4
Passo indutivo.
Usando a relação de Fibonacci,
Usando a relação de Fibonacci,
Pela hipótese de indução, substituímos
e
. Primeiro,
Em seguida, note que
também pela hipótese (aplicada a
, válida para
; no caso
já tratamos na base). Logo,
Agrupando termos com
e com
,
Mas pelas próprias recorrências de Fibonacci,
Portanto,
que é exatamente o que queríamos. Isso fecha o passo indutivo.
Resposta
A identidade
é verdadeira para todos os inteiros não negativos
e
.