Considere
a sequência de Fibonacci. Mostre que:
;
Passo 1
Beleza, vamos provar a identidade da sequência de Fibonacci
Conteúdo: sequência de Fibonacci e prova por indução
O que a gente vai usar:
Conteúdo: sequência de Fibonacci e prova por indução
O que a gente vai usar:
- Definição da sequência:
- Princípio da indução matemática
Passo 2
Primeiro, confere o caso base
:
Lado esquerdo:
Lado esquerdo:
Lado direito:
Como deu
, o caso base está ok.
Passo 3
Agora, suponha que a fórmula vale para algum
, ou seja:
A gente quer mostrar que vale para
. Então calcula:
Pela hipótese de indução o somatório até
é
. E pela definição de Fibonacci:
Substituindo:
Por outro lado, o que queremos é
Mas usando a recursão duas vezes:
Logo
que bate exatamente com o que encontramos para
. Assim a indução fecha.