Re: [obm-l] fibonacci

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

On Mon, Mar 06, 2006 at 04:45:21PM -0300, filipe junqueira wrote:
>   Nicolau Saldanha escreveu sobre uma demonstração duma expressão que 
> envolvia os numeros da sequencia do fibo. Citou uma expressão em que F(n)= 
> a^n  -   b^n/sqrt5  : a=(1+sqrt5)/2 e b=(1-sqrt5)/2. GOstaria de saber como 
> demonstrar ou de onde vem essa expressão que define f(n)?!!!

Muita gente já respondeu (eu inclusive) mas há um método interessante
que não foi apresentado.

Escreva f(z) = F(0) + F(1) z + F(2) z^2 + ... + F(k) z^k + ...
Escreva agora
(z + z^2) f(z) = 
        F(0) z + F(1) z^2 + F(2) z^3 + ... + F(k-1) z^k + ...
                 F(0) z^2 + F(1) z^3 + ... + F(k-2) z^k + ...

   (usando que F(k-1) + F(k-2) = F(k) e que F(0) = 0)

=                F(2) z^2 + F(3) z^3 + ... + F(k)   z^k + ...

   (usando que F(0) = 0, F(1) = 1)

= f(z) - z

Assim f(z) = z/(1-z-z^2) = -z/((z+a)(z+b))

onde, como antes, a = (1+sqrt(5))/2, b = (1-sqrt(5))/2.

Queremos agora escrever f(z) = C/(z+a) + D/(z+b).
Expandindo temos
f(z) = (Cz+Cb+Dz+Da)/((z+a)(z+b)) = ((C+D)z + (Cb+Da))/((z+a)(z+b)) 
donde C+D = -1, bC+aD = 0 donde C = -a/sqrt(5), D = b/sqrt(5).
Ou seja,
f(z) = 1/sqrt(5) ( - a/(a+z) + b/(b+z) )
   (como 1/a = -b, 1/b = -a)
     = 1/sqrt(5) ( 1/(1-az) - 1/(1-bz) )

Por outro lado, sabemos (pg infinita) que
1/(1-az) = 1 + a z + a^2 z^2 + ... + a^k z^k + ...
1/(1-bz) = 1 + b z + b^2 z^2 + ... + b^k z^k + ...

Assim
f(z) = 1/sqrt(5) ( (a-b) z + (a^2-b^2) z^2 + ... + (a^k-b^k) z^k + ... )
que dá a fórmula desejada para F(k).

[]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
=========================================================================