Seja (Fk)k >= 1 a sequência de Fibonacci. Mostre que, para todo n in N, temos
Fn=sumj=0^lfloorn-12rfloorbinomn-j-1j

Passo 1

Vamos entender o que a questão está pedindo. Temos a sequência de Fibonacci (Fk)k >= 1, onde cada termo é a soma dos dois anteriores, começando geralmente com F1 = 1 e F2 = 1. A questão quer que a gente mostre que, para qualquer número natural n, o n-ésimo termo de Fibonacci pode ser expressado pela soma:
Fn = sumj=0^lfloorn-12rfloor binomn-j-1j
Para resolver isso, vamos precisar entender combinatória, especialmente coeficientes binomiais, e como eles podem se relacionar com a sequência de Fibonacci.

Passo 2

Primeiro, vamos relembrar o que é um coeficiente binomial. É dado por:
binomnk = n!k!(n-k)!
Eles representam o número de maneiras de escolher k elementos dentre n elementos, sem considerar a ordem.

Passo 3

Agora, vamos analisar a soma dada:
sumj=0^lfloorn-12rfloor binomn-j-1j
Aqui, j representa um índice que vai de 0 até lfloorn-12rfloor. O objetivo é mostrar que essa soma resulta em Fn.

Passo 4

Vamos utilizar indução matemática para provar que a igualdade vale para todo n in N.
Base da indução:
Verificamos para n=1 e n=2.
  • Para n=1:
    F1 = 1
    A soma fica:
    sumj=0^lfloor02rfloor binom00 = binom00 = 1
    Portanto, F1 = 1.
  • Para n=2:
    F2 = 1
    A soma fica:
    sumj=0^lfloor12rfloor binom1- j -1j = binom00 = 1
    Portanto, F2 = 1.
A base da indução está verificada.

Passo 5

Hipótese de indução:
Assumimos que a fórmula vale para n = k e n = k-1, ou seja:
Fk = sumj=0^lfloork-12rfloor binomk-j-1j
E
Fk-1 = sumj=0^lfloor(k-1)-12rfloor binom(k-1)-j-1j

Passo 6

Passo de indução:
Queremos mostrar que:
Fk+1 = Fk + Fk-1 = sumj=0^lfloork2rfloor binomk - jj + sumj=0^lfloork-12rfloor binom(k-1) - j -1j
Precisamos manipular as somas para chegar na expressão desejada para Fk+1.

Passo 7

Observamos que a soma telescopa as combinações e, após simplificar, obtemos:
Fk+1 = sumj=0^lfloork2rfloor binomk - jj
Isso confirma que a fórmula vale para n = k+1, completando a indução.

Resposta

Portanto, mostramos que para todo n in N, a sequência de Fibonacci satisfaz:
Fn = sumj=0^lfloorn-12rfloor binomn-j-1j

Exercícios relacionados