Re: [obm-l] Fibonacci

["Marcio" <marciocohen@xxxxxxxxxxxxxx>]

Oi Cláudio.. A idéia que eu mencionei antes funciona bastante bem nesse
caso.
    Afinal, se a,b, a>b são as raízes de x^2 = x+1, sabemos que F_n = (a^n -
b^n)/sqrt(5). Como ab=-1:
    Se n eh par, entao 1/sqrt(5)F_n = 1 / [(-1/b)^n - b^n] = b^n / [1 -
b^(2n)] = b^n + b^(3n) + b^(5n) + ...
(como |b|<1, podemos interpretar a fração como a soma da pg que começa em
b^n e tem razao b^(2n) ).
    Variando n entre as potências de dois pares e somando temos:
n=2:    b^2 + b^6 + b^10 + b^14 +...        (expoente = 2 (mod4))
n=4:    b^4 + b^12 + b^20 +...                  (expoente = 4 (mod8)
n=8:    b^8 + b^24 + ...        (expoente = 8 (mod16))
...
Note que todo expoente par aparece uma e apenas uma vez nessa soma (de fato,
se X = (2^r)i, com i ímpar, então X = 2^r (mod 2^(r+1)), e
X != 2^k (mod 2^(k+1)) para outros valores de k - se k<r ok, pq da zero. Se
k>r tmb, pq isso implicaria que 2^k | X, contradizendo i ser impar ).

Logo, [1/sqrt(5)] * [1/F_2 + 1/F_4 + 1/F_8 + 1/F_16 + ...] = b^2 + b^4 + b^6
+ ... = b^2 / (1-b^2)
Sendo S a soma procurada: S - 1/F_1 = sqrt(5) * b^2 / (1-b^2).
Como b = [1-sqrt(5)]/2 e b^2 = 1+b:
S = 1 - sqrt(5)*b = 1-sqrt(5)* ( 1-sqrt(5))/2 = (2 - sqrt(5) + 5)/2 =
(7-sqrt(5))/2.

Note que os passos em que se trocou ordem de somatório são formalmente
justificados pelo fato de soh termos tratados de series absolutamente
convergentes de termos positivos (pois b^2 > 0).

Abraco,
Marcio

----- Original Message -----
From: "Claudio Buffara" <claudio.buffara@terra.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Saturday, April 12, 2003 3:41 PM
Subject: Re: [obm-l] Fibonacci


> Oi, Marcio:
>
> Mesmo o problema de se achar:
> S = SOMA(n>=0) 1/F(2^n)
> esta' longe de ser trivial.
>
> Eu sei que S = 4 - A, onde A = (1 + raiz(5))/2, ou seja,
> S = (7 - raiz(5))/2.
>
> Acho que a formula: F(2k) = [F(k+1) + F(k-1)]*F(k) deve entrar em algum
> lugar na demonstracao e, de algum jeito, a restricao as potencias de 2
deve
> fazer aparecer alguma PG cuja soma eh S.
>
> Um abraco,
> Claudio.
>
>

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