A sequência de Fibonacci
é definida por:
Prove usando indução finita que
.
Passo 1
Então, o exercício quer que a gente prove, por indução finita (indução forte), que a sequência de Fibonacci
satisfaz
O conteúdo é Indução (forte) e a gente vai precisar:
- Verificar as bases (pegar
e ). - Formular a hipótese indutiva (supondo a desigualdade para todos os índices até
). - Mostrar que daí ela vale para
.
Passo 2
(Base da indução)
Para :
Para
logo
. OK.
Para
:
logo
. Também OK.
Assim, a propriedade vale para
e
.
Passo 3
(Indução forte)
Suponha que, para todo com
, valha
Suponha que, para todo
Queremos mostrar
.
Usando a definição de Fibonacci:
Pela hipótese indutiva,
Então
Para concluir, basta ver que
que é verdade. Logo
Resposta
Por indução forte, mostramos que para todo
vale