Prove que
. Conclua a partir daí que
são múltiplos de 5 .
Passo 1
O enunciado trata da sequência de Fibonacci
, dada por
e pede para provar que
e, a partir disso, concluir que
são múltiplos de 5.
Vamos usar um argumento por indução forte sobre .
Vamos usar um argumento por indução forte sobre
Passo 2
Base da indução: verificamos manualmente para
e
.
- Para
:
logo
.
- Para
:
logo
.
Portanto, a propriedade vale para e
.
Portanto, a propriedade vale para
Passo 3
Passo indutivo: suponha que para todo
com
tenhamos
Queremos mostrar
isto é,
Usando a relação de recorrência,
e também
, obtemos
Pela hipótese indutiva,
divide cada um dos dois parênteses, logo também divide sua soma. Assim,
. Isso fecha a indução forte, provando que
Passo 4
Agora, para concluir que
são múltiplos de 5, note que, para
, a propriedade dá
Mas
. Supondo
, segue
. Por indução em
, todos os termos
são múltiplos de 5.
Resposta
Está provado que