Combinatorics question?Fibonacci sequence.Please help as soon as possible.

If {Fn,n∈N} is the Fibonacci sequence,prove that every natural number k∈N can be written UNIQUELY as K=Fm1+Fm2+Fm3+.....+Fm(r) such that m11
Thanks in advance.

This Theorem is true.

Michael's counterexample is incorrect because it uses the sequence 3 + 5, which contains two consecutive Fibonacci numbers. This is explicitly forbidden by the condition for i < j: mj - mi > 1.


------

The theorem has two parts: existence and uniqueness. We prove them separately.

-------

We start with existence, which we prove by strong induction on k. For k=1, k = F1, so we are done.

Suppose this fact is true for all natural numbers less than k. We prove it for k. If k is of the form Fn for some n, we are done. If not, find the largest Fn such that Fn < k < F(n+1). By induction, k-Fn can be written as Fm1 + Fm2 +... +Fm(r) with m1 < m2 < ... < m(r) and for i < j: mj - mi > 1. Clearly, then, we can add to this set the new number Fm(r+1) = Fn. Because (k - Fn) < (F(n+1) - Fn) = F(n-1), it is obvious that n > m(r). Further, m(r) cannot equal n-1 (otherwise (k - Fn) >= F(n-1), which is contradictory), so we also maintain the property that for all i < j: mj - mi > 1.

This completes the proof of existence.

-------

Now to the uniqueness. We first show that for any sequence of the form Fm1, Fm2, ..., Fm(r) satisfying m1 < m2 ... < mr and for i 1, we must have Fm1 + Fm2 + ... + Fm(r) < F(m(r) + 1). This we do by induction on r.

For r = 1, we want to prove that Fm1 < F(m1 + 1). This is clear because Fibonacci numbers increase monotonically.

Suppose that the fact is true for r. We show it for r+1 as follows:

Fm1 + ... + Fm(r) + Fm(r+1)
< F(m(r) + 1) + Fm(r+1) -- by induction hypothesis

Now, because m(r+1) - m(r) >= 2,
m(r+1) - [m(r) + 1] >= 1.
So, m(r)+1 <= m(r+1) - 1

Continuing the earlier proof, we have: