[obm-l] Re: [obm-l] Somatório de Fibonacci com binomio de Newton

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Fri, Jan 10, 2003 at 03:14:00PM -0300, Carlos Maçaranduba wrote:
> Alguem poderia fazer a questão abaixo?????
> 
>  Seja F_n o enésimo número de fibonacci.Seja C_x,y a
> combinação de x elementos tomados y a y(x maior ou
> igual a y).Prove o somatório abaixo:
> 
> C_n,0*(F_1) + C_n,1*(F_2) +....C_n,n*(F_n+1) = F_2n+1.

O bom é provar uma identidade bem mais geral:

C_n,0 * F_m + C_n,1 * F_m+1 + ... + C_n,n * F_m+n = F_2n+m

que pode ser provada por indução em n. O caso n = 0 é trivial:

C_0,0 * F_m = F_0+m

e o caso n = 1 é fácil:

C_1,0 * F_m + C_1,1 * F_m+1 = F_m+2

Supondo o caso n temos

C_n,0 * F_m   + C_n,1 * F_m+1 + C_n,2 * F_m+2 + ... + C_n,n * F_m+n                     = F_2n+m
                C_n,0 * F_m+1 + C_n,1 * F_m+2 + ... + C_n,n-1 * F_m+n + C_n,n * F_m+n+1 = F_2n+m+1

e somando as duas equações casando do lado esquerdo termos
onde o F_* tem o mesmo índice
(na vertical para quem a minha diagramação funcionar)
temos

C_n+1,0 * F_m + C_n+1,1 * F_m+1 + C_n+1,2 * F_m+2 + ... + C_n+1,n * F_m+n + C_n+1,n+1 * F_m+n+1 = F_2n+m+2

que é o caso n+1.

[]s, N.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================