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

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

  • $\begingroup$ 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 𝑓𝑛? $\endgroup$ – mathlover Dec 28 '19 at 12:55
  • $\begingroup$ that is the induction hypothesis $\endgroup$ – Jorge Fernández Hidalgo Dec 28 '19 at 23:06

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.