# 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 – Sidd Singal 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

## 2 Answers

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$.

Proving uniqueness (which is true only with the restriction that the Fibonacci numbers used be non-consecutive) takes a little more work, and in any case you weren’t asked to do it. Still, you might find it interesting to try. You might also find some of the odds and ends here interesting.

Hint: Induction! (Start from $n=4$)

• Note: This is known as Zeckendorf's Theorem – Juan S Sep 17 '12 at 23:05
• This even allows that the Fibonacci numbers used are not sequential. – Ross Millikan Sep 17 '12 at 23:15
• I assume by "sequential" you mean something that I would call "adjacent"? – Ben Millwood Sep 17 '12 at 23:19