Considere
a sequência de Fibonacci. Mostre que:
;
Passo 1
Beleza, aqui o que a gente quer é mostrar que, para a sequência de Fibonacci
, vale a fórmula
O conteúdo envolvido é:
- Definição da sequência de Fibonacci (
, , ). - Princípio de indução matemática, que é uma ferramenta para provar afirmações para todo
.
Passo 2
Primeiro, vamos entender a prova por indução:
- Base da indução: mostrar que a fórmula funciona para o menor valor de
(aqui ). - Passo de indução: assumir que a fórmula vale para algum
e então provar que ela vale para .
Base (
):
Do outro lado, a fórmula diz
pois
. Então para
tá tudo certo.
Passo 3
Agora vem a mágica da indução.
Hipótese de indução: suponha que, para algum
, valha
Queremos mostrar que daí segue
Começamos escrevendo a soma até
como soma até
mais o termo
:
Pela hipótese de indução,
. Então
E a gente conhece a definição de Fibonacci:
Logo
que é exatamente o que a gente queria provar no passo de indução.
Como a base deu certo e o passo de indução também, concluímos que a fórmula vale para todo
.