# 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 $$. 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\ge 4$ and that every integer less than $k$ is a sum of distinct Fibonacci numbers. Let $n$ be the largest positive integer such that $$. We first note that if $k-{F}_{n}>{F}_{n-1}$ then

$${F}_{n+1}\ge k>{F}_{n}+{F}_{n-1}={F}_{n+1},$$ |

giving us a contradiction^{}. Hence $k-{F}_{n}\le {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 $$.
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 |