proof that every positive integer has a Zeckendorf representation
Otherwise, we assign where is the largest Fibonacci number such that . Then . It is obvious that , because it can be safely assumed at this juncture that and are distinct, that and therefore . This proves that must be 1, but no more than that. If is a Fibonacci number, we can stop now, otherwise, we must again subtract the largest possible Fibonacci number, decrement accordingly and set the appropriate . The farthest this iterative process can go is to , corresponding to .
Furthermore, the 1s in must have 0s in between them because any two consecutive 1s, such as at, say, and would indicate a failure to recognize that , and thus and can be set to zero in favor of setting 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|
|Date of creation||2013-03-22 16:36:43|
|Last modified on||2013-03-22 16:36:43|
|Last modified by||PrimeFan (13766)|