Sejam
e
(
é chamado de n-ésimo número de Fibonacci). Mostrar que
Passo 1
O enunciado pede pra provar que, na sequência de Fibonacci definida por
vale a igualdade
Estamos trabalhando com somas de produtos de termos de Fibonacci e vamos usar indução matemática e a própria relação de recorrência
.
Passo 2
Primeiro, vamos mostrar que a afirmação vale para
(caso base).
Para a soma tem só dois termos:
Para
Do outro lado,
Então, de fato,
e o caso base está confirmado.
Passo 3
Agora assumimos que a fórmula vale para um certo
, ou seja,
Vamos provar que daí decorre que ela vale para
.
A soma até pode ser vista como
A soma até
Pela hipótese de indução, a parte até
é
. Logo
Agora usamos a relação
para juntar os dois últimos termos:
Repare que
Então
que é exatamente a fórmula para
. Assim finalizamos o passo de indução.
Resposta
Portanto, por indução, mostramos que para todo
vale