Fibonacci Sequence Property

Date: 11/29/2001 at 05:35:36
From: Enrique Somolinos
Subject: Demonstration of a Fibonacci sequence property

Hi,

I have to demonstrate a particular property of the Fibonacci 
sequence: 

Let F(k) be the k number of the Fibonacci sequence. I have to prove 
that F(k) is a divisor of F(nk), where n is a natural number (so, 
F(nk) = A*F(k) where A is a natural number). I have tried my best but 
I can't find a way to demonstrate this.

Can you help me please?
Thank you in advance,
Enrique

Date: 11/29/2001 at 10:58:17
From: Doctor Rob
Subject: Re: Demonstration of a Fibonacci sequence property

Thanks for writing to Ask Dr. Math, Enrique.

You can prove this by using the addition formula for the Fibonacci
numbers:

   F(r+s) = F(r-1)*F(s) + F(r)*F(s+1),

together with the Principle of Mathematical Induction on the variable 
k.

If you don't know how to prove the above formula, you can do that by
fixing s and using induction on r. Alternatively, you can use the
Binet Formula for the Fibonacci numbers:

   F(t) = (a^t-b^t)/(a-b),
   a = (1+sqrt[5])/2,
   b = (1-sqrt[5])/2,
   a^2 = a + 1,
   b^2 = b + 1.

When this is substituted in the addition formula, and everything is
simplified, you will see that it is reduced to an identity.

Feel free to write again if I can help further.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/