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

• how do you know (I am not understanding why this is true) that you can Since 𝑘 is under 𝑓𝑛 we can write 𝑘as a sum of distinct Fibonacci numbers not including 𝑓𝑛? – mathlover Dec 28 '19 at 12:55
• that is the induction hypothesis – Jorge Fernández Hidalgo Dec 28 '19 at 23:06