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

### Like this:

Like Loading...

*Related*

Tags: fibonacci, math, theorem

This entry was posted on November 19, 2008 at 7:22 pm and is filed under math, theorem. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply