*16. Demonstre o Teorema 3.
17. Demonstre a identidade abaixo relacionada aos números de Fibonacci e aos coeficientes binomiais:
f_{n+1}=C(n, 0)+C(n-1,1)+\cdots+C(n-k, k),
em que n é um número inteiro positivo e k=\lfloor n / 2\rfloor. [Dica: Considere a_{n}=C(n, 0)+C(n-1,1)+\cdots+C(n-k, k). Mostre que a seqüência \left\{a_{n}\right\} satisfaz a mesma relação de recorrência e as condições iniciais da seqüência dos números de Fibonacci.]

Passo 1

O enunciado pede para demonstrar a identidade
f_{n+1} = C(n,0) + C(n-1,1) + \cdots + C(n-k,k),
onde n é inteiro positivo, k = \lfloor n/2\rfloor e f_m são os números de Fibonacci. O método sugerido é mostrar que a soma dos binomiais satisfaz a mesma recorrência de Fibonacci e as mesmas condições iniciais.

Passo 2

Defina
a_n = \sum_{i=0}^k \binom{n-i}{i}, \qquad k = \lfloor n/2\rfloor.
Verifiquemos as condições iniciais da sequência \{a_n\}:
Para n=0 tem-se k=0 e
a_0 = \binom{0}{0} = 1 = f_1.
Para n=1 também k=0 e
a_1 = \binom{1}{0} = 1 = f_2.

Passo 3

Mostremos que a_n satisfaz a recorrência de Fibonacci para n\ge2. Pela identidade de Pascal,
\binom{n-i}{i} = \binom{n-1-i}{i} + \binom{n-1-i}{i-1}.
Logo
a_n = \sum_{i=0}^k \binom{n-i}{i} = \sum_{i=0}^k \Bigl(\binom{n-1-i}{i} + \binom{n-1-i}{i-1}\Bigr).
Separando as somas,
\sum_{i=0}^k \binom{n-1-i}{i} = a_{n-1},
e, fazendo j=i-1 na segunda soma,
\sum_{i=1}^k \binom{n-1-i}{i-1} = \sum_{j=0}^{k-1} \binom{n-2-j}{j} = a_{n-2}.
Portanto
a_n = a_{n-1} + a_{n-2}.

Passo 4

Temos que \{a_n\} e \{f_{n+1}\} satisfazem a mesma relação de recorrência
x_n = x_{n-1} + x_{n-2}
e coincidem nas condições iniciais n=0,1. Pelo princípio da indução, segue que
a_n = f_{n+1} \quad\text{para todo }n\ge0.

Resposta

f_{n+1} = \sum_{i=0}^{\lfloor n/2\rfloor} \binom{n-i}{i}.

Exercícios de Livros Relacionados