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
[Math] Every natural number can be written as the sum of distinct Fibonacci numbers
elementary-number-theoryfibonacci-numbers
Best Answer
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.