Fibonacci Number basis Induction The Fibonacci numbers are defined as follows:
$$F_1 = 0, \quad
F_2 = 1, \quad
F_n = F_{n−2} + F_{n−1}, \text{ for all } n \geq 3$$
Prove the following using induction:

Zeckendorf's theorem. One can express any positive integer as a sum of distinct
  Fibonacci numbers, no two of which have consecutive Fibonacci indices. For example,
  $79 = 55 + 21 + 3$.

We will prove this claim by using induction on $n$.
IH: Assume that the claim is true when $n = k$, for some $k > 3$.
$F_k = F_{k−2} + F_{k−1}$
BC: k = 3
Am I on the right track for this? Not sure where to go from here
 A: It is perhaps better to suppose that the claim is true for $n\le k$ for some $k\ge$, say $3$, (it is easy to check for $k=1, 2, 3$).
Let us consider $n=k+1$. 
If $n=F_j$ for some $j$, then the claim is true. 
Otherwise, let us suppose $F_j<n<F_{j+1}$. Let $n'=n-F_j$. Then $n'<F_{j+1}-F_j=F_{j-1}$. 
By assumption, we can express $n'=\sum_{i\in I} F_i$. It is clear that $i<j-1$.
It is your job to verify that $n=n'+F_j=\sum_{i\in I} F_i+F_j$ is the desire expression.
Therefore the claim holds for $n$.
A: Suppose by induction any number between $1$ and $f_n$  can be written as a sum of distinct Fibonacci numbers, we shall prove any number between $1$ and $f_{n+1}$ can be written as distinct Fibonacci numbers. We must only prove it for numbers between $f_n$ and $f_{n+1}$
Pick such a  number $a$ between $f_n$ and $f_{n+1}$, it can be written as $f_n+k$ where $k$ is a number between $1$ and $f_{n-1}$ by the definition of Fibonacci. Since $k$ is under $f_n$ we can write $k$ as a sum of distinct Fibonacci numbers not including $f_n$. So when we add the Fibonacci numbers in $k$ with $f_n$ we get the desired way to write $a$.
