6.7 CONTINUANTS 293 Well, y must be
irrational, because of a little-known Einsteinian assertion: “God does not throw huge
denominators at the universe.”
Therefore nobody believes that y is rational; but nobody so far has been able to prove that it isn’t. Let’s conclude this chapter by proving a remarkable identity that ties a lot of these ideas together. We introduced the notion of spectrum in Chapter 3; the spectrum of OL is the multiset of numbers Ln&], where 01 is a given constant. The infinite series
can therefore be said to be the generating function for the spectrum of @, where @ = (1 + fi)/2 is the golden ratio. The identity we will prove, discovered in 1976 by J.L. Davison [61], is an infinite continued fraction that relates this generating function to the Fibonacci sequence: (6.143)
Both sides of (6.143) are interesting; let’s look first at the numbers Ln@J. If the Fibonacci representation (6.113) of n is Fk, + . . . + Fk,, we expect n+ to be approximately Fk, +I +. . . + Fk,+i , the number we get from shifting the Fibonacci representation left (as when converting from miles to kilometers). In fact, we know from (6.125) that
n+ = Fk,+, + . . . + Fk,+l - ($“I + . + q”r) . Now+=-l/@andki >...>>k,>>O,sowehave
and qkl +.. .+$jkl has the same sign as (-1) kr, by a similar argument. Hence In+] = Fk,+i +.‘.+Fk,+l - [ k , ( n ) iseven].
(6.144)
Let us say that a number n is Fibonacci odd (or F-odd for short) if its least significant Fibonacci bit is 1; this is the same as saying that k,(n) = 2. Otherwise n is Fibonacci even (F-even). For example, the smallest F-odd