Well,
The problem itself is comparatively easy but I can not resist to write about such an interesting series.
Problem : Let, F(n) denote a function which returns n-th number in Fibonacci series. Prove that for all n,
F(k) | F(nk).
Solution : Again my beloved friend “principle of mathematical induction” comes to the rescue :-).
Base case : n=1, F(k) | F(k) ( a | b denotes that “a divides b” or in other words “b is a multiple of a” ). Trivially true.
Induction Hypothesis : Assume that F(k) | F( nk-k)
F(nk-k) = F((n-1)k). So assume that the claim is correct for (n-1).
Induction Step :
F(nk) = F(nk-1) + F(nk -2 )
= 2F(nk-2 ) + F(nk-3)
= 3F(nk-3) + 2F(nk-4)
= 5(nk-4) + 3F(nk-5)
(A) = F(i)F(nk-i+1) + F(i-1)F(nk-i) (This generalization is also as easy to prove as this property)
I can take values from 1 to nk. For n=1 we have already proved. So n will be at least 2.
2k >= k+1
Therefore, Let i be k+1
(A) = F(k+1) F(nk – k -1 + 1) + F(k) F(nk-k-1)
= F(k+1) F(nk – k ) + F(k) F(nk – k – 1)
First term is a mutiple of F(k) due to induction hypothesis.
Hence, F(k) | F(nk).
If you are interested in knowing something more about Fibonacci numbers, visit this page and/or visit the wikipedia link given at the beginning of this post.
— Saurabh Joshi
Leave a comment