Fibonacci Number basis Induction

Question

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

Answer 1

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

Answer 2

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