Fibonacci
Representation of numbers
The question we want to answer is, whether each positive integer can be written as a sum of different Fibonacci numbers.
We will show that for each positive integer m all numbers less than
Fm+2 may be written as sum of different
terms from the sequence F1, F2,
..., Fm.
It is simple to check that the statement is correct for m=1.
Suppose we have already shown that the statement is correct for
m=1,2,3,...,n. Is there a recipe that gives us the correctness for m=n+1?
Yes, namely by adding Fn+1 to the representations of the
numbers Fn,Fn+1,...,Fn+2-1.
That gives us the extra numbers Fn+2,Fn+2+1,...,Fn+3-1.
Thus now all numbers less than Fn+3 are represented using the terms
F1, F2, ..., Fn+1.
In the same way we may show the correctness of the statement for m=n+2
using the correctness for m=1,2,...,n+1, and so on.