We all know about Fibonacci sequence. in general: F(n) = F(n-1) + F(n-2). Can you prove that: F(2n)/F(n) is an integer? i.e. F(2n) is divisible by F(n)

Thanks,

I know of two ways to do this.

One is to use Binet's formula for the n^th term of the sequence, and then prove that the resulting horrible mess is an integer. This is not particularly good fun.

Another is to use modular arithmetic. Try writing out the values of F_n+1 , F_n+2 and so on mod F_n , and keep going - if I remember correctly there is a general pattern that will allow you to write down F_2n mod F_n and show it is zero.

David

Start from F(2n) and back substitute:

F(2n)=F(2n-1)+F(2n-2)
=2F(2n-2)+F(2n-3)
=3F(2n-3)+2F(2n-4)
.......

and you end up with,

F(2n)=F(n)(F(n+1)+F(n-1)).

Ian

The resulting sequence is a Fibonnaci type sequence that you would get starting from the numbers g(1)=1 and g(2)=3.

Where g(n)=F(2n)/F(n).

Ian

In other words, it is the Lucas sequence.

David

F(n)=(tⁿ-t^-n)/Ö5

where t=(1+Ö5)/2 is the golden ratio. So we have

F(2n)/F(n)=(tⁿ+t^-n)

Now consider the map sending a+bÖ5 to a-bÖ5, a and b rational. This leaves the expression unchanged, so F(2n)/F(n) is rational (which you know already, but is not terribly obvious with all the t's lying around). Further, since t is a unit in the quadratic field Q(Ö5) (its minimal polynomial being X²-X-1), F(2n)/F(n) must also be an algebraic integer, which gives F(2n)/F(n) a rational integer. This method also tells you that you have the Lucas numbers.

Kerwin

By Andre Rzym on Sunday, November 10, 2002 - 09:41 pm:

Ngoc,

Your original problem can be generalised somewhat, namely to "If m is divisible by n, then F_m is divisible by F_n ".

Taking the modular arithmetic approach (as David describes) gives you this result straightforwardly.

Andre

Thanks everyone for helping,
I got it now.