Fibonacci Numbers and Zeckendorf’s Theorem

Paying with strange coins#

Imagine a country whose coins are worth 1, 2, 3, 5, 8, 13, 21, 34, 55 and so on. Each coin is the sum of the two before it. You want to pay any amount, using each coin at most once, and never two coins that sit next to each other in that list.

Can you always do it? Yes, and in exactly one way. That is Zeckendorf’s theorem. This page shows the method, then the proof your professor gave.

The Fibonacci sequence#

Start with F₀ = 0 and F₁ = 1. After that, each term is the sum of the previous two: F_n = F_n−1 + F_n−2. A rule like that, which builds each term from earlier ones, is called a recurrence.

Two checkpoints from the lecture catch most slips: F₅ = 5 and F₁₀ = 55. If your table disagrees at either spot, you started the indexing wrong.

One property worth knowing: if m divides n, then F_m divides F_n. For example 5 divides 10, and F₅ = 5 divides F₁₀ = 55. Likewise 3 divides 9, and F₃ = 2 divides F₉ = 34.

The theorem, stated carefully#

Zeckendorf’s theorem. Every whole number n ≥ 1 can be written as

n = F_k₁ + F_k₂ + … + F_kₗ

where the indices k₁ > k₂ > … > kₗ satisfy two rules:

• No two are consecutive. Each index is at least 2 below the one before it.
• The smallest index is at least 2. F₁ is not allowed.

Why ban F₁? Because F₁ = F₂ = 1. With F₁ allowed, 3 could be written as F₄ and also as F₃ + F₁ = 2 + 1, and the representation would not be unique.

The method: always take the biggest coin that fits#

To write n, find the largest Fibonacci number that is ≤ n. Subtract it. Repeat on what is left.

Example: 50. The largest Fibonacci number ≤ 50 is 34 = F₉, leaving 16. The largest ≤ 16 is 13 = F₇, leaving 3 = F₄. So

50 = F₉ + F₇ + F₄ = 34 + 13 + 3. The indices 9, 7, 4 never touch.

The small cases from the lecture, which also serve as the base cases of the proof:

Why this needs strong induction#

In ordinary induction you prove the case n + 1 using only the case n. Here that is not enough.

To handle 50 you subtract 34 and need a representation of 16, not of 49. The number you need is the leftover after the biggest subtraction, and it can be far below n. You do not know in advance which one it will be.

Strong induction fixes this. Its hypothesis assumes the statement for every case from the start up to n, not only for n itself. Then whatever leftover you land on, you are allowed to use it. Strong induction is logically equivalent to ordinary induction; it simply hands you more to work with.

The proof, step by step#

Basis step. The table above checks n = 1 through 11 directly.

Induction hypothesis. Let n ≥ 11 and assume every m with 1 ≤ m ≤ n has a representation of the required kind.

Goal. Show that n + 1 has one.

Let F_k₁ be the largest Fibonacci number with F_k₁ ≤ n + 1.

Case 1: F_k₁ = n + 1. Then n + 1 is itself a Fibonacci number, a one-term representation. Done.

Case 2: F_k₁ < n + 1. Let m = n + 1 − F_k₁. Then m ≥ 1, and m ≤ n because F_k₁ ≥ 1. So the induction hypothesis applies to m:

m = F_k₂ + … + F_kₗ, with non-consecutive indices.

Add F_k₁ back: n + 1 = F_k₁ + F_k₂ + … + F_kₗ.

The last thing to check is that k₂ is not next to k₁, that is, k₂ ≤ k₁ − 2. Suppose not, so k₂ ≥ k₁ − 1. Fibonacci numbers increase, so

n + 1 ≥ F_k₁ + F_k₂ ≥ F_k₁ + F_k₁−1 = F_k₁+1.

The last step is the Fibonacci rule itself. But then F_k₁+1 is a bigger Fibonacci number that still fits under n + 1, which contradicts choosing F_k₁ as the largest. So k₂ ≤ k₁ − 2.

Conclusion. By the principle of strong mathematical induction, every n ≥ 1 has a Zeckendorf representation. The lecture left uniqueness for another video; the same “largest term” idea is the heart of that proof too.

Where this goes wrong#

• Starting small instead of big. 1 + 2 + 3 = 6 uses consecutive terms. The greedy method must take the largest term first.
• Using consecutive terms that happen to sum correctly. 34 + 8 + 5 + 3 = 50, but 8 and 5 are neighbours. Merge them into 13.
• Using F₁. It duplicates F₂ and breaks uniqueness.
• Writing the hypothesis as ordinary induction. “Assume it holds for n” does not cover the leftover m. Write “for every m with 1 ≤ m ≤ n”.
• Forgetting the non-consecutive check. Existence of some Fibonacci sum is easy. The contradiction argument is what earns the marks.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.