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)?!!!

A expressão correta é F(n) = (a^n - b^n)/sqrt(5).
Note que a^2 = a + 1, b^2 = b + 1.

Vamos primeiro verificar que qualquer seqüência da forma
g(n) = C a^n + D b^n (onde C e D são constantes) satisfaz a relação
g(n+2) = g(n+1) + g(n). De fato, basta expandir:
g(n+2) = C a^(n+2) + D a^(n+2) = C a^n a^2 + D b^n b^2 =
C a^n (a + 1) + D b^n (b + 1) = C a^(n+1) + C a^n + D b^(n+1) + D b^n =
(C a^(n+1) + D b^(n+1)) + (C a^n + D b^n) = g(n+1) + g(n).
Agora, tomando C = 1/sqrt(5) e D = -1/sqrt(5) podemos verificar que
g(0) = C + D = 1/sqrt(5) - 1/sqrt(5) = 0,
g(1) = C a + D b = (1+sqrt(5))/(2 sqrt(5)) - (1-sqrt(5))/(2 sqrt(5)) =
(sqrt(5)+5-sqrt(5)+5)/(2*5) = 10/10 = 1.
Assim, g(0) = F(0), g(1) = F(1). Podemos provar por indução que g(n) = F(n)
para todo n: g(n+2) = g(n+1) + g(n) = F(n+1) + F(n) = F(n+2).

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