Fred wrote [of the Wikipedia article on Zeckendorf's theorem]:

<< Also mentioned there is a "Fibonacci product", . . . with x = \sum_i a_i F_i, y = \sum_j b_j F_j,

(*) x(*)y = \sum_{i,j} a_i b_j F_{i+j} .

Knuth reputedly proved this operation to be associative, which Wikipedia finds surprising. Apparently it follows immediately from . . . . . . --- so after all, Knuth's theorem is surprising!

...

...

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).

unless i'm overlooking something, this is (almost) obvious. the definition of "Fibonacci product" does not really necessitate that the expressions x = \sum_i a_i F_i and y = \sum_j b_j F_j are in Zeckendorf form; that is, the operation is well-defined even without this condition. indeed, any two such expressions for x can be transformed to one another by a sequence of replacing a_i F_{i+2} by a_i (F_{i+1} + F_i) or vice-versa; the corresponding term a_i b_j F_{i+j+2} in the product is then replaced by a_i b_j (F_{i+j+1} + F_{i+j}) . (i'm supposing here that the coefficients are all integers, but i'm not sure of their significance; in view of Zeckendorf's theorem, might one want them all to be 1 ?) and then of course, either parenthesization of x(*)y(*)z gives \sum_{i,j,k} a_i b_j c_k F_{i+j+k} . mike