Seja
a sequência de Fibonacci definida por
e
. Demonstre os seguintes itens:
.
Passo 1
O enunciado define a sequência de Fibonacci por
e pede para demonstrar, para todo
, que
O método que vamos usar é indução sobre
, mantendo
fixo.
Passo 2
(Base da indução) Para
a fórmula vira
Como
, o lado direito é
que é exatamente
pela definição da sequência. Logo a base
vale.
Passo 3
(Hipótese de indução) Suponha que para algum
valha
Passo 4
(Passo indutivo) Queremos mostrar que
Começamos usando a recorrência de Fibonacci em
:
Pelo passo anterior, substituímos
Somando estes dois resultados:
Agora agrupamos:
E como
e
, obtemos
que é exatamente o que queríamos. Isso fecha o passo indutivo.
Resposta
A identidade
vale para todo
por indução em
.