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).