Main Index Number Theory Sequences Recurrent sequences Linear recurrent sequences Binary recurrent sequences Lucas’ sequences Fibonacci Numbers
Subject Index
comment on the page

Knuth (Fibonacci) product

Zeckendorf's theorem states that every positive integer typeset structure can be uniquely represented way as the sum of one or more distinct Fibonacci numbers typeset structure in such a way that the sum does not include any two consecutive Fibonacci numbers, that is

N = Underoverscript[∑, i = 0, arg3] F _ n _ i , where n _ 1 > n _ 2 > ... > n _ k >= 2

Using this representation we can define a new product of two integers [1] : If typeset structureand typeset structure are two positive integers then their Knuth (also called Fibonacci) product is defined by

N o M = Underoverscript[∑, i = 0, arg3] Underoverscript[∑, t = 0, arg3] F _ (n _ i + m _ t) .

Knuth proved that this product is associative.  If we change the definition in such a way that we define

N°M = Underoverscript[∑, i = 0, arg3] Underoverscript[∑, t = 0, arg3] F _ (n _ i + m _ t - 2)

then this product is not associative. On the other hand, 1 is a multiplicative identity in typeset structure product but not in the typeset structure product.

References

[1]  Knuth, D. E. (1988). Fibonacci multiplication. Appl. Math. Lett., 1, 57-60.

Cite this web-page as:

Štefan Porubský: Knuth multiplication.

Page created  .