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 $0, 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 $F_{i}. Then $Z_{i}>0$. It is obvious that $j, because it can be safely assumed at this juncture that $F_{i-2}$ and $F_{i-1}$ are distinct, that $F_{i-2} and therefore $F_{i}<2F_{i-1}$. 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 ProofThatEveryPositiveIntegerHasAZeckendorfRepresentation 2013-03-22 16:36:43 2013-03-22 16:36:43 PrimeFan (13766) PrimeFan (13766) 5 PrimeFan (13766) Proof msc 11A63 msc 11B39