How about this approach? Lemma $ 1$ Lets prove by induction that every integer can be written as the sum of some different fibonacci numbers. It is true for $ n=1=f_1$ Assume that it is true for $ n$ then if $ f_1$ is not in the sum of $ n$ we are done, add it and we obtain a sum for $ n+1$ suppose that $ f_1,f_2, \cdots,f_{i-1},f_i$ are in the sum of $ n$ and $ f_{i+1}$ is not then you can replace by pairs $ (f_{i-1},f_i) \rightarrow f_{i+1}$ $ (f_{i-3},f_{i-2}) \rightarrow f_{i-1}$ replacing either $ f_2$ or $ (f_2$ and $ f_1)$ depending on the parity of $ i$ and add $ f_2$ and we obtain a sum for $ n+1$ From the lemma $ 1$ we can applying the following rule to obtain the desired sum: $ (f_{i-1},f_i) \rightarrow f_{i+1}$ with $ i$ maximum index such as $ (f_{i-1},f_i)$ are in the sum and $ f_{i+1}$ is not in the sum.

Assume that each number less than or equal to $ f_n$ satisfies the condition. We want to prove that this implies all numbers between $ f_n$ and $ f_{n+1}$ satisfy the condition. Each number in this interval can be written as: $ f_n+k$ where $ k<f_{n+1}-f_{n}$ and so $ k<f_{n-1}$. But by induction all the $ k$ can be represented as a sum of fibonaci numbers all stricly less than $ f_{n-1}$. Hence by writing $ k$ in this form, all the $ f_n+k$ satisfy the condition, and so does $ f_{n+1}$ trivially, completing the induction

As the small-print caption of the topic mentions, this is Zeckendorf's theorem, see http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem. The simplest proof is by the greedy algorithm, see also above posts.