# proof that every positive integer has a Zeckendorf representation

Theorem. Every positive integer $n$ has a Zeckendorf representation^{} as a sum of non-consecutive Fibonacci numbers^{} ${F}_{i}$.

If an integer $n={F}_{k}$, where ${F}_{x}$ refers to a Fibonacci number, then ${Z}_{k}=1$ and ${Z}_{i}=0$ for all $$, where $Z$ is an array of binary digits and $k$ is the index of the most significant digit.

Otherwise, we assign $j=n-{F}_{i}$ where ${F}_{i}$ is the largest Fibonacci number such that $$. Then ${Z}_{i}>0$. It is obvious that $$, because it can be safely assumed at this juncture that ${F}_{i-2}$ and ${F}_{i-1}$ are distinct, that $$ and therefore $$. This proves that ${Z}_{i}$ must be 1, but no more than that. If $j$ is a Fibonacci number, we can stop now, otherwise, we must again subtract the largest possible Fibonacci number, decrement $i$ accordingly and set the appropriate ${Z}_{i}=1$. The farthest this iterative process can go is to $i=1$, corresponding to ${F}_{1}=1$.

Furthermore, the 1s in $Z$ must have 0s in between them because any two consecutive 1s, such as at, say, ${Z}_{i}$ and ${Z}_{i-1}$ would indicate a failure to recognize that ${F}_{i-1}+{F}_{i}={F}_{i+1}$, and thus ${Z}_{i}$ and ${Z}_{i-1}$ can be set to zero in favor of setting ${Z}_{i+1}$ to 1. (As a side note, no binary representation of a Mersenne number should be mistaken for a Zeckendorf representation; in other words, there are no repunits^{} in Zeckendorf representations).

Title | proof that every positive integer has a Zeckendorf representation |
---|---|

Canonical name | ProofThatEveryPositiveIntegerHasAZeckendorfRepresentation |

Date of creation | 2013-03-22 16:36:43 |

Last modified on | 2013-03-22 16:36:43 |

Owner | PrimeFan (13766) |

Last modified by | PrimeFan (13766) |

Numerical id | 5 |

Author | PrimeFan (13766) |

Entry type | Proof |

Classification | msc 11A63 |

Classification | msc 11B39 |