# 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

• First, you should not reuse $n$ from the definition of the Fibonacci numbers. You need to prove it for $1$, (otherwise it might not be true for all positive integers), so that might as well be your base case: Just say $1=F_2$ You need to distinguish between the number you are expressing and the index of the Fibonacci numbers, $k$ appears both ways. – Ross Millikan Nov 2 '14 at 15:54

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

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 fibonaccis in $k$ with $f_n$ we get the desired way to write $a$.