On 5/16/08, Dan Asimov <dasimov@earthlink.net> wrote:
I, too, first thought this associativity obvious, merely because addition (of indices) is associative . . . but this is specious (I think) since there's nothing to guarantee the RHS of (*) is in Zeckendorf form (which requires no repeated or consecutive indices).
A couple of errors (surprise, surprise) crept into a proof I gave, which should read: Uniqueness of the representation is proved by induction: given natural x with F_n <= x < F_{n+1}, assume every natural y < F_n is uniquely representable as a sum of non-consecutive F_k with 1 < k < n; note that no y >= F_n is so representable; apply assumption to y = x - F_n, noting that y < F_{n-1}. The case x = 0 is plainly representable by the empty sum; however, see below ... The theorem on Fibonacci product associativity in Wikipedia turns out even more surprising than I earlier appreciated --- as quoted there, it's false! More precisely for x > 1, (1(*)1) (*) x <> 1 (*) (1(*)x) , x (*) (1(*)1) <> (x(*)1) (*) 1 . I don't know whether Knuth's paper mentions this irritating anomaly, or how to fix it; but the following "base-F'" kludge seems to work. Though the convention k >= 2 employed earlier is the natural one, an alternative is to attach two further digits at the less-significant end, that is summing over k >= 0: with this scheme, we might instead represent (including redundant left-hand zeros) in base-10, 20 = 13+5+2 = F_7 + F_5 + F_3 = ...010101000 in base-F' . There is some arbitrariness about the value of the extra pair --- define them to be 00 for x > 1, but in base-10, 1 = ...0101 in base-F' ; in base-10, 0 = ...0001 in base-F' . [0 could instead be represented by ...0000 --- this would in turn redefine Fibonacci product, from x(*)0 = x to x(*)0 = 0 as originally.] Fred Lunnon