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

For any positive integer, $k\in\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.