Hogatt’s theorem

Hogatt’s theorem states that every positive integer can be expressed asa 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.