# Fibonacci induction

The question requires strong induction.

Prove that a sum of a set of Fibonacci numbers can represent any natural number n.

For example, 49 is the sum of a set (34, 13, 2) of Fibonacci numbers.

I understand how this makes sense, but I wasn't sure what values to use as the base case.

• Wouldn't you either use $(1)$ or $(0)$ as the base case, depending on if you defined the Naturals to be include $0$ or not? – Melody Nov 7 '18 at 2:58
• If my base cases are 1, 2, 3, then the sets of Fibonacci numbers would only contain one element – aryamank Nov 7 '18 at 3:04
• I don't think so. If you start the Fibonacci Numbers at $1$ being the first and $1$ being the second, then regardless of the fact that the only number the $\{F_1\}$ can sum to is $1$ you can still produce infinitely many Fibonacci numbers. – Melody Nov 7 '18 at 3:08

You don't need strong induction to prove this. Consider the set of all numbers that cannot be expressed as a sum of Fibonacci numbers.

If this set were non-empty, it would have a smallest element $$n_0$$.

Now let $$F_n$$ be the largest Fibonacci number $$< n_0$$. Then $$n_0 - F_n < n_0$$ and thus $$n_0 - F_n$$ is a sum of Fibonacci numbers. Thus $$n_0$$ is also a sum of Fibonacci numbers. Contradiction.

Therefore there is no number that is not a sum of Fibonacci numbers.

Added: It is possible to prove that each $$n \ge 2$$ can be uniquely written as a sum of distinct Fibonacci numbers such that no two consecutive Fibonacci numbers appear in the sum. For example, $$20 = 13 + 5 + 2$$ and $$200 = 144 + 55 + 1$$ (Fibonacci Coding). Proof by strong induction.

• The question requires it to be proved by strong induction, though – aryamank Nov 7 '18 at 3:22
• Fortunately, the least-number principle used in this answer is easily equivalent to strong induction, so the answer can be written in a way that uses strong induction. – Andreas Blass Nov 7 '18 at 3:25
• Unfortunately, the question said "the sum of a set of Fibonacci numbers" not just "a sum of Fibonacci numbers"; the difference is that there should be no repeated summands. (If repetitions were allowed, you could just use a sum of 1's.) So the answer needs to be supplemented with a (fortunately easy) argument that $F_n$ is not needed as a summand in $n_0-F_n$ (because in fact $F_n>n_0-F_n$). – Andreas Blass Nov 7 '18 at 3:28
• My bad; I edited the question now. I understand that I should do n - Fk, where Fk is the largest Fibonacci number in a set. But then I am not sure how to approach it. – aryamank Nov 7 '18 at 3:34