Exercise 1758Logic, sets and proofs › Proof techniques › InductionOlympiadAdded 3 Nov 2026

Every positive integer is a sum of non-consecutive Fibonacci numbers

#induction#Fibonacci#Zeckendorf

Statement

Prove Zeckendorf's theorem: every positive integer can be expressed uniquely as a sum of non-consecutive Fibonacci numbers (with $F_2=1,F_3=2,\ldots$ ).

Hint

Use strong induction: for $n$ , pick the largest $F_k\le n$ and apply induction to $n-F_k$ .

Show solutionHide solution

Solution

Existence. Strong induction on $n$ . Choose $F_k$ the largest Fibonacci number $\le n$ . Then $n-F_k<F_{k-1}$ (otherwise $F_k+F_{k-1}=F_{k+1}\le n$ , contradicting maximality of $F_k$ ). By induction, $n-F_k$ is a sum of non-consecutive Fibonacci numbers with all indices $<k-1$ . Adding $F_k$ gives a valid representation.

Uniqueness. Suppose two representations differ; use the recurrence $F_k>F_{k-1}+\cdots+F_1$ for appropriate cases to derive a contradiction.

Conclusion. Zeckendorf representations exist and are unique.

Every positive integer is a sum of non-consecutive Fibonacci numbers

Statement

Solution

More problems in Induction