Proof by induction that if $n \in \mathbb N$ then it can be written as sum of different Fibonacci numbers 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? 
 A: 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}$.
A: (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.
A: 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.
A: 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.
