Sejam
e
, tal que
(
é chamado o n-ésimo número de Fibonacci). Mostre que:
Passo 1
O enunciado define a sequência de Fibonacci por
e pede para mostrar que
Vamos usar o princípio de indução matemática para provar essa fórmula.
Passo 2
Base da indução:
.
À esquerda temos
À esquerda temos
e à direita
Como
, segue que
Logo a fórmula vale para
.
Passo 3
Hipótese de indução: suponha que para algum
valha
Passo 4
Passo de indução: queremos mostrar que
Observe que
e, pela hipótese de indução,
Então
Mas pela definição de Fibonacci
logo
Passo 5
Concluímos por indução que a fórmula
é verdadeira para todo
.