Re: Fibonacci

["José Paulo Carneiro" <jpcarneiro@xxxxxxxxxxxxxxx>]

Caro Eric:
(Veja abaixo)

-----Mensagem original-----
De: Eric Campos <mathfire@uol.com.br>
Para: Lista da OBM <obm-l@mat.puc-rio.br>
Data: Sexta-feira, 24 de Dezembro de 1999 00:36
Assunto: Fibonacci


>O seguinte problema foi proposto por Jose Paulo Carneiro
>
>As duas sequencias:
>1, 1, 2, 3, 5, 8, 13, ...
>e
>1, 3, 4, 7, 11, ...
>
>Sao ambas tais que cada termo eh a soma dos dois anteriores.
>Observacoes: a segunda sequencia eh chamada "sequencia de Lucas".
>
>Mostre que:
>
>dado um inteiro positivo arbitrario m, existe sempre algum termo da
>primeira sequencia que eh multiplo de m.
>
>Imaginei uma solucao assim:
>
>seja f(i) o i-esimo termo da sucessao de Fibonacci 1, 1, 2, 3, 5, 8, 13,
>..., em que cada termo eh a soma dos dois anteriores. Seja m um inteiro
>generico. Considere a funcao g(n) = resto de f(n) quando dividido por m,
com
>g(n) nao negativo. Eh claro que g eh uma sucessao, pois g esta definida no
>conjunto dos naturais. Como ha no maximo m distintos valores possiveis para
>g(n), ha no maximo m^2 distintos possiveis pares de inteiros consecutivos
na
>sucessao g. Portanto existem inteiros positivos i,k para os quais
>(g(i),g(i+1)) = (g(i+k),g(i+k+1)), isto eh, existem dois pares de numeros
de
>Fibonacci consecutivos que tem o mesmo resto (positivo) na divisao por m.
>Nesse caso como g(i) + g(i+1) = g(i+k) + g(i+k+1) temos em particular que
>g(i+2) = g(i+k+2),

*********
Ateh aqui, eu estava concordando plenamente com voce.
*********

e de modo mais geral g(n) = g(n + k) para cada n inteiro
>positivo.

*********
Agora, este passo nao estah claro para mim. So sabiamos isto para n
particulares, da forma i+2.
Se fizermos "experiencias", com m=2,3,4,5,6,..., vamos observar que
o par de restos que repete primeiro eh sempre o (1,1). Isto sugere o
seguinte caminho que proponho:
Seja i* o menor i para o qual ocorre a igualdade (g(i),g(i+1)) =
(g(i+k),g(i+k+1)).
Se i*>1, entao, como g(i*+1)=g(i*)+g(i*-1)  e g(i*+k+1)=g(i*+k)+g(i*+k-1),
conclui-se que g(i*-1)=g(i*+1)-g(i*)=g(i*+k-1)=g(i*+k+1)-g(i*+k).
Mas entao, o par (g(i*+k-1), g(i*+k)) ja repetiria o apr (g(i*-1), g(i*)), o
que eh
absurdo, pois contraria a definicao de i*. Logo, i*=1.
Agora sim: temos: (g(1), g(2))=(1,1)=(g(k+1), g(k+2)) . Logo:
g(k)=g(k+2)-g(k+1)=1-1=0, e portanto g(k) eh multiplo de m.

Jose Paulo
**********

logo 1 = g(1) = g(1 + k) e 1 = g(2) = g(2 + k), donde g(k) = g(2 +
>k) - g(1 + k) = 0, isto eh, m divide f(k).
>
>Eric.
>

A partir daquele ponto, sugiro o seguinte: