As I understand it, there are at least three proofs that if n divides m, then f_n divides f_m , where f_n is the nth Fibonacci number. Does anyone know any of them?

Thanks for any help.

Here is a sketch of a proof. Let me know if any blanks need filling in (I am assuming you have come across modular arithmetic):

If F(n) is the nth Fibonacci number, then consider what the sequence looks like mod F(n). Clearly, the nth term will be zero mod F(n).

Now F(1)=1 and F(2)=1. Can you see that if we had started with F(1)=k and F(2)=k for any integer, k, that the nth term of that series would still be zero modulo F(n)?

Now think about what the n+1th and n+2th terms of the Fibonacci series are modulo F(n). Can you see that they are equal?

Can you therefore see that F(2n) must also be zero mod F(n)? We can keep repeating the argument to show F(3n), F(4n) etc are similarly equal to 0 mod F(n).

In other words, F(n) divides F(m) where m is a multiple of n.

Andre

There is a second way of proving it, if you care:

As you know, the Fibonacci numbers obey the recurrence relationship: F(n+2)=F(n)+F(n-1)

Look for an explicit solution of the form
F(n)=pⁿ . Substituting into the difference equation above gives p=(1+5^0.5 )/2,p=(1-5^0.5 )/2.

Call these values a & b. Fitting F(1)=F(2)=1 gives us:
F(n)=(1/5^0.5 )(aⁿ -bⁿ ).

If we now consider F(m)/F(n) (your original question) we have

F(m)/F(n)=(a^m -b^m )/(aⁿ -bⁿ )

Provided m is a multiple of n this factors algebraically:

F(m)/F(n)= a^m-n +(a^m-2n )(bⁿ )+...+b^m-n

Finally, you need to convince yourself that this polynomial in a,b is actually an integer. You can do this by looking at the symmetry of the result with respect to a & b and the form of a and b. An alternative route is to observe that ab=-1 (an integer), and that a^k +b^k is an integer for all integer k.

Andre

And for a third alternative, it follows immediately from the explicit formula:

F_n = L_k F_n-k - (-1)^k F_n-2k

where L_k is the kth Lucas number, given by F_k+1 + F_k-1 . This is derived somewhere in the following discussion .