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

  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.