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.

  • $\begingroup$ 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? $\endgroup$ – Melody Nov 7 '18 at 2:58
  • $\begingroup$ If my base cases are 1, 2, 3, then the sets of Fibonacci numbers would only contain one element $\endgroup$ – aryamank Nov 7 '18 at 3:04
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ The question requires it to be proved by strong induction, though $\endgroup$ – aryamank Nov 7 '18 at 3:22
  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Nov 7 '18 at 3:25
  • $\begingroup$ 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$). $\endgroup$ – Andreas Blass Nov 7 '18 at 3:28
  • $\begingroup$ 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. $\endgroup$ – aryamank Nov 7 '18 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.