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<i<k$ , 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}<n$ . Then $Z_{i}>0$ . It is obvious that $j<F_{i}$ , because it can be safely assumed at this juncture that $F_{i-2}$ and $F_{i-1}$ are distinct, that $F_{i-2}<F_{i-1}$ 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
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