Hogatt’s theorem

Hogatt’s theorem states that every positive integer can be expressed as a sum of distinct Fibonacci numbers.

For any positive integer, $k\in\mathbb{Z}^{+}$ , there exists a unique positive integer $n$ so that $F_{n-1}<k\leq F_{n}$ . We proceed by strong induction on $n$ . For $k=0,1,2,3$ , the property is true as $0,1,2,3$ are themselves Fibonacci numbers. Suppose $k\geq 4$ and that every integer less than $k$ is a sum of distinct Fibonacci numbers. Let $n$ be the largest positive integer such that $F_{n}<k$ . We first note that if $k-F_{n}>F_{n-1}$ then

F_{n+1}\geq k>F_{n}+F_{n-1}=F_{n+1},

giving us a contradiction. Hence $k-F_{n}\leq F_{n-1}$ and consequently the positive integer $(k-F_{n})$ can be expressed as a sum of distinct Fibonacci numbers. Moreover, this sum does not contain the term $F_{n}$ as $k-F_{n}\leq F_{n-1}<F_{n}$ . Hence, $k=(k-F_{n})+F_{n}$ is a sum of distinct Fibonacci numbers and Hogatt’s theorem is proved by induction.

Title	Hogatt’s theorem
Canonical name	HogattsTheorem
Date of creation	2013-03-22 13:43:24
Last modified on	2013-03-22 13:43:24
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	8
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 11B39
Related topic	FibonacciSequence