Sejam F1=1, F2=1 e Fn=Fn-1+Fn-2, n >= 3 ( Fn é chamado de n-ésimo número de Fibonacci). Mostrar que
F1+F2+F3+cdots+Fn=Fn+2-1

Passo 1

Beleza, vamos lá! O enunciado diz que os Fibonacci são
Fn = Fn-1 + Fn-2 , F1 + F2 + cdots + Fn = Fn+2 - 1 e, para ,
A tarefa é mostrar que
Isso é um típico problema de prova por indução (teoria da indução matemática). A ideia é:
  1. Mostrar que a fórmula vale para um caso inicial (base).
  2. Assumir que vale para e mostrar que daí ela vale para .

Passo 2

Base da indução ( F3 = F2 + F1 = 1 + 1 = 2, ):
O lado esquerdo é só F1 = 1 = F3-1, .
O lado direito é . Como
ficamos com .
Então, para temos
logo a fórmula funciona no caso base.

Passo 3

Passo indutivo: suponha que, para algum F1 + F2 + cdots + Fn = Fn+2 - 1 ,
F1 + F2 + cdots + Fn + Fn+1 = F(n+1)+2 - 1 = Fn+3 - 1
Chamamos isso de hipótese de indução. Agora precisamos provar que

Passo 4

Usando a hipótese de indução, o lado esquerdo com (F1 + cdots + Fn) + Fn+1 = l(Fn+2 - 1r) + Fn+1, termos fica
Fn+3 = Fn+2 + Fn+1
pela hipótese. Agora lembramos que, pela definição de Fibonacci,
l(Fn+2 - 1r) + Fn+1 = Fn+2 + Fn+1 - 1 = Fn+3 - 1
Então
Isso mostra exatamente o que queríamos para .

Resposta

Portanto, por indução, concluímos que para todo boxedF1 + F2 + cdots + Fn = Fn+2 - 1 :

Exercícios relacionados