# Every natural number can be written as the sum of distinct Fibonacci numbers?

Can anyone hint me to prove:

$\forall n\in \mathbb{N}: \exists$ Fibonacci numbers $F_{i_1},\ldots,F_{i_k}$ such that: $$\sum F_{i_k}=n$$

Note: Every Fibonacci number can appear only once. Thanks

-
Is there any conditions on the numbers? Since $F_1 = 1$, we have $\underbrace{F_1 + \ldots + F_1}_{\textrm{n times}} = n$ – sxd Sep 17 '12 at 23:01
Well $1 \in F_n$ so... – Juan S Sep 17 '12 at 23:01
The title does say "different" Fibonacci numbers – mathguy Sep 17 '12 at 23:02
We are only allowed to use every Fibonacci number, at most once. – Hooman Sep 17 '12 at 23:02
@Hooman, write that in the body of your question then as well! – sxd Sep 17 '12 at 23:03

In fact every positive integer can be written uniquely as a sum of one or more non-consecutive Fibonacci numbers; this is known a Zeckendorf’s theorem. There is even a simple algorithm for finding this representation: just use the greedy algorithm, always picking the largest Fibonacci number that will still ‘fit’. E.g., $32=21+8+3$. This fact should suggest that a proof by induction might work: if $n$ is not a Fibonacci number, and $F_k$ is the largest Fibonacci number less than $n$, look at $n-F_k$.
Hint: Induction! (Start from $n=4$)