combinatorial proof of Zeckendorf’s theorem
(Ignoring is necessary only to prevent the trivial counterexamples such as ).
Given a sum where , we write that as a sequence of binary digits; thus is written as , while is . Arrange such sequences with no two consecutive ’s (i.e. those sequences corresponding to sums of nonconsecutive Fibonacci numbers) in increasing lexicographic order starting from , and assign each one a rank corresponding to its order in the list:
Note that the rank is not the value of the string as a binary string. In fact, it is the sum of the string when interpreted as a sum of Fibonacci numbers, but we do not assume this; as far as we know up to this point, all the rank is is the row number in this table.
We say that such a sequence has length if the leftmost is in position ; thus has length .
Claim that the number of representations with length is . We prove this by induction on ; note that it is true for and for . Now, given any representation of length , it either has length or it has length exactly . The number of representations of length is, by induction, . To compute the number of representations of length exactly , note that any such representation starts with since we cannot have two consecutive ’s. The digits after the are arbitrary as long as there are not two consecutive ’s, so that the number of such representations is precisely the number of representations of length , or . Thus the number of representations of length is . This proves the claim.
We will now prove the theorem by counting the number of rows preceding row in two different ways. First, the number of such rows is obviously (since we just numbered the row consecutively). We now count the number of predecessors by looking at the corresponding sequence. Given a sequence , each of its predecessors first differs from it in some position ; since lexicographically, must be in that position while is zero. Since has a zero in position , the remaining digits of are arbitrary subject to the consecutivity condition, so the number of possibilities for is the number of representations of length , which is . We can do this for each possible point of difference with (which occur at the positions in which has a , and thus must have nonconsecutive indices). This counts each predecessor of once and only once, and gives a representation of the number of predecessors as a sum of nonconsecutive Fibonacci numbers. But there are predecessors, so we have written as the required sum.
As an example of this process, consider the row numbered , which is the sequence . If a predecessor differs from it at the first , it is of the form where the ’s are arbitrary (so long as there are no two consecutive ’s, so there are of them. If a predecessor differs from it at the second , it is of the form and again the ’s are arbitrary, so there are of them. Thus .
|Title||combinatorial proof of Zeckendorf’s theorem|
|Date of creation||2013-03-22 19:05:53|
|Last modified on||2013-03-22 19:05:53|
|Last modified by||rm50 (10146)|