Sejam
e
(
é chamado de n-ésimo número de Fibonacci). Mostrar que
Passo 1
Beleza, vamos lá! O enunciado diz que os Fibonacci são
,
e, para
,
A tarefa é mostrar que
Isso é um típico problema de prova por indução (teoria da indução matemática). A ideia é:
- Mostrar que a fórmula vale para um caso inicial (base).
- Assumir que vale para
e mostrar que daí ela vale para .
Passo 2
Base da indução (
):
O lado esquerdo é só .
O lado direito é . Como
O lado esquerdo é só
O lado direito é
ficamos com
.
Então, para temos
Então, para
logo a fórmula funciona no caso base.
Passo 3
Passo indutivo: suponha que, para algum
,
Chamamos isso de hipótese de indução. Agora precisamos provar que
Passo 4
Usando a hipótese de indução, o lado esquerdo com
termos fica
pela hipótese. Agora lembramos que, pela definição de Fibonacci,
Então
Isso mostra exatamente o que queríamos para
.
Resposta
Portanto, por indução, concluímos que para todo
: