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, para todo inteiro
,
O método mais direto aqui é o da indução matemática sobre
.
Passo 2
Base da indução (
):
O lado esquerdo é
O lado esquerdo é
e o lado direito é
Portanto a igualdade vale para
.
Passo 3
Hipótese de indução: suponha que, para algum
, já seja verdade que
Passo 4
Passo indutivo (
):
Considere a soma até . Temos
Considere a soma até
Pela hipótese de indução, o parêntese vale
. Logo
Mas a própria definição de Fibonacci dá
de onde
Assim mostramos que a fórmula vale para
.
Passo 5
Pelo princípio da indução matemática, a identidade
é verdadeira para todo inteiro
.