Seja Fn a sequência de Fibonacci definida por F1=F2=1 e Fn+2=Fn+1+Fn, n >= 1. Demonstre os seguintes itens:
Fn+m=Fn-1 Fm+Fn Fm+1.

Passo 1

O enunciado define a sequência de Fibonacci por
F1=F2=1, Fn+2=Fn+1+Fn(n>=1)
e pede para demonstrar, para todo n,m>=1, que
Fn+m=Fn-1,Fm+Fn,Fm+1
O método que vamos usar é indução sobre m, mantendo n fixo.

Passo 2

(Base da indução) Para m=1 a fórmula vira
Fn+1stackrel?=Fn-1,F1+Fn,F2
Como F1=F2=1, o lado direito é
Fn-1cdot1 + Fncdot1 = Fn-1+Fn,
que é exatamente Fn+1 pela definição da sequência. Logo a base m=1 vale.

Passo 3

(Hipótese de indução) Suponha que para algum m>=1 valha
Fn+m=Fn-1,Fm+Fn,Fm+1

Passo 4

(Passo indutivo) Queremos mostrar que
Fn+(m+1)=Fn-1,Fm+1+Fn,Fm+2
Começamos usando a recorrência de Fibonacci em Fn+m+1:
Fn+m+1=Fn+m+Fn+m-1
Pelo passo anterior, substituímos
Fn+m=Fn-1Fm+FnFm+1, Fn+m-1=Fn-1Fm-1+FnFm
Somando estes dois resultados:
Fn+m+1 =l(Fn-1Fm+FnFm+1r) +l(Fn-1Fm-1+FnFmr)
Agora agrupamos:
Fn+m+1 =Fn-1l(Fm+Fm-1r) +Fnl(Fm+1+Fmr)
E como Fm+Fm-1=Fm+1 e Fm+1+Fm=Fm+2, obtemos
Fn+m+1 =Fn-1Fm+1+FnFm+2,
que é exatamente o que queríamos. Isso fecha o passo indutivo.

Resposta

A identidade
Fn+m=Fn-1,Fm+Fn,Fm+1
vale para todo n,m>=1 por indução em m.

Exercícios relacionados