proof that every positive integer has a Zeckendorf representation

Theorem. Every positive integer n has a Zeckendorf representationMathworldPlanetmath as a sum of non-consecutive Fibonacci numbersDlmfMathworldPlanetmath Fi.

If an integer n=Fk, where Fx refers to a Fibonacci number, then Zk=1 and Zi=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-Fi where Fi is the largest Fibonacci number such that Fi<n. Then Zi>0. It is obvious that j<Fi, because it can be safely assumed at this juncture that Fi-2 and Fi-1 are distinct, that Fi-2<Fi-1 and therefore Fi<2Fi-1. This proves that Zi 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 Zi=1. The farthest this iterative process can go is to i=1, corresponding to F1=1.

Furthermore, the 1s in Z must have 0s in between them because any two consecutive 1s, such as at, say, Zi and Zi-1 would indicate a failure to recognize that Fi-1+Fi=Fi+1, and thus Zi and Zi-1 can be set to zero in favor of setting Zi+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 repunitsMathworldPlanetmath 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