# 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}. 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}. 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}. 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 HogattsTheorem 2013-03-22 13:43:24 2013-03-22 13:43:24 mathcam (2727) mathcam (2727) 8 mathcam (2727) Theorem msc 11B39 FibonacciSequence