Proof that every natural number $n\in \mathbb N$, can be written as the sum of different Fibonacci numbers between $F_2,F_3,\ldots,F_k,\ldots$.

For example: $32 = 21 + 8+3 = F_8+F_6+F_4$

Research effort:

The base step it's simple:

Let $k=1$ it can be britten as $k=1=F_2$

For the inductive step I considered:

Let $k = k F_2 =F_2+F_2+\cdots+F_2 = \sum_{i=2}^w a_iF_i, a_i =\{0,1\} $

Then if $k$ suffice I want to see if $k+1$ suffices too... But I'm not realy seeing how to use the inductive hypothesis, so I assume It's wrong.

Any thoughts on which can the inductive step be?


You need to use generalized induction:

If $$ \text{$P_k$ is true for all $k\in \mathbb N$ with $k<n$} \implies P_n $$ then $$ \text{$P_n$ is true for all $n\in \mathbb N$} $$

Then you apply the idea suggested in the other answers. To represent the number $n$ you take the largest $F_i$ such tht $F_i\le n$. Then apply the induction hypothesys on $n-F_i$. The point is to notice that $n - F_i< F_i$ because $F_i < 2 F_{i-1}$.


Hint: Let $F_\ell$ be the largest Fibonacci number $\le k$. Apply induction hypothesis to $k-F_\ell$. Observe that you still need to make sure that all the used Fibonacci numbers will be different.

  • $\begingroup$ I still can't see how to solve it, mind giving me some more help? $\endgroup$ – FranckN Mar 6 '14 at 16:39
  • 1
    $\begingroup$ Others have already expanded on this. The main point is that $k-F_\ell$ will be smaller than $F_{\ell-1}$, so continuing in this way will not produce repetitions of Fibonacci numbers. $\endgroup$ – Jyrki Lahtonen Mar 6 '14 at 18:37

You don't even need induction at all to prove this!

First note that for any $n>0$ there's always $F_k$ such that $\frac n2<F_k\leq n$. It holds for $n=1$, else take highest $F_k\leq\frac n2$, then $F_k\geq1$, so $\frac n2<F_{k+1}\leq2F_k\leq n$.

Now suppose not every number can be written like that and take the lowest $n$. But according to the previous result, there's $F_k$ such that $\frac n2<F_k\leq n$.

Now $n-F_k$ can be written as a sum of different Fibonacci numbers according to our choice of $n$, but this means $n$ can be written too, because $n-F_k>n-\frac n2=\frac n2$, so the other Fibonacci numbers were less or equal to $\frac n2$ and therefore less than $F_k$, so we have a contradiction.


(Zeckendorf's Proof:) Assume it to be true for all integers up to and including $F_n$ , and let $F_{n+1} \ge N > F_n$ . Now, $N = F_n +(N−F_n)$, and $N \le F_{n+1} < 2F_n$ , i.e., $N−F_n < F_n$. Thus $N − F_n$ can be written in the form $F_{t_1} +\ldots+ F_{t_r}$,

$N − F_n < t_{i+1} \le t_{i}−2$, $t_r \ge 2$,

and $N = F_n + F_{t_1} + F_{t_2} +\ldots+F_{t_r}$.

We can be certain that $n \ge t_1 + 2$, because, if we had $n = t_1 + 1$, then $F_n=F_{t_1+1}+2F_n$ . But this is larger than N. In fact, $F_n$ must appear in the representation of $N$ because no sum of smaller Fibonacci numbers, obeying $k_{i+1} \le k_i − 2$, $(i=1,2,\ldots,r − 1)$ and $k_r ≥ 2$, could add up to $N$.

This follows, if $n$ is even, say $2k$, from $F_{2k−1} + F_{2k−3} +\ldots+ F_3= (F_{2k} − F_{2k−2}) + (F_{2k−2} − F_{2k−4}) +\ldots+ (F_4 − F_2)$, which is $F_{2k}−1$, and if $n$ is odd, say $2k − 1$, it follows from $F_{2k} + F_{2k−2} +\ldots+ F_2=(F_{2k+1} − F_{2k−1}) +\ldots+(F_3−F_1)=F_{2k−1} − 1$.

Again, the largest $F_i$ not exceeding $N − F_n$ must appear in the representation of $N − F_n$ , and it cannot be $F_{n−1}$ . Note that this proves uniqueness by induction.


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.