Proof by induction that if $n \in \mathbb N$ then it can be written as sum of different Fibonacci numbers

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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