09 Seja F_{n} a sequência de Fibonacci definida por F_{0}=0, F_{1}=1 e
F_{n+2}=F_{n+1}+F_{n}
para todo inteiro não negativo n.
Mostre que, para todos os inteiros não negativos n, m,
F_{n+m+1}=F_{n} F_{m}+F_{n+1} F_{m+1}

Passo 1

O enunciado trata da sequência de Fibonacci (F_n)_{n\ge0} definida por
F_{0}=0,\quad F_{1}=1,\quad F_{n+2}=F_{n+1}+F_{n}.
Queremos mostrar, para quaisquer inteiros não negativos n e m, que
F_{n+m+1}=F_{n}F_{m}+F_{n+1}F_{m+1}.
O método escolhido será a indução sobre m, mantendo n fixo.

Passo 2

Base da indução m=0.
No lado esquerdo temos
F_{n+0+1}=F_{n+1}.
No lado direito,
F_{n}F_{0}+F_{n+1}F_{0+1} =F_{n}\cdot 0 + F_{n+1}\cdot 1 =F_{n+1}.
Logo, a fórmula vale para m=0.

Passo 3

Hipótese de indução.
Suponha que, para algum m\ge0, valha
F_{n+m+1}=F_{n}F_{m}+F_{n+1}F_{m+1}.
Queremos então provar que
F_{n+(m+1)+1} =F_{n}F_{m+1}+F_{n+1}F_{m+2}.

Passo 4

Passo indutivo.
Usando a relação de Fibonacci,
F_{n+(m+1)+1} =F_{n+m+2} =F_{n+m+1}+F_{n+m}.
Pela hipótese de indução, substituímos F_{n+m+1} e F_{n+m}. Primeiro,
F_{n+m+1} =F_{n}F_{m}+F_{n+1}F_{m+1}.
Em seguida, note que
F_{n+m} =F_{n+(m-1)+1} =F_{n}F_{m-1}+F_{n+1}F_{m}
também pela hipótese (aplicada a m-1, válida para m\ge1; no caso m=0 já tratamos na base). Logo,
F_{n+m+2} =\bigl(F_{n}F_{m}+F_{n+1}F_{m+1}\bigr) +\bigl(F_{n}F_{m-1}+F_{n+1}F_{m}\bigr).
Agrupando termos com F_{n} e com F_{n+1},
F_{n+m+2} =F_{n}\bigl(F_{m}+F_{m-1}\bigr) +F_{n+1}\bigl(F_{m+1}+F_{m}\bigr).
Mas pelas próprias recorrências de Fibonacci,
F_{m}+F_{m-1}=F_{m+1}, \quad F_{m+1}+F_{m}=F_{m+2}.
Portanto,
F_{n+m+2} =F_{n}F_{m+1}+F_{n+1}F_{m+2},
que é exatamente o que queríamos. Isso fecha o passo indutivo.

Resposta

A identidade
F_{n+m+1}=F_{n}F_{m}+F_{n+1}F_{m+1}
é verdadeira para todos os inteiros não negativos n e m.

Exercícios relacionados