Considere a sucessão de Fibonacci, definida por recorrência,
Mostre, usuando indução, que
Passo 1
Estamos lidando com a sequência de Fibonacci, definida por recorrência:
O que queremos provar por indução é a identidade
Passo 2
Base da indução: para
. Calculamos
e isso coincide com
. Logo, a base está válida.
Passo 3
Passo indutivo: suponha que para um
seja verdade
Devemos mostrar que
Passo 4
Usando a relação de recorrência
, desenvolvemos:
Note que
e como
temos
Pela hipótese indutiva essa expressão vale (-(-1)^{k}) = (-1)^{k+1}.
Passo 5
Concluímos, portanto, que se a identidade vale para
então vale para
. Como a base e o passo indutivo estão estabelecidos, a fórmula é verdadeira para todo
.