Some remarks about Fibonacci multiplication. (English) Zbl 0711.11008
The Fibonacci sequence is defined recursively by the formula \(F_{i+2}=F_ i+F_{i+1}\) for \(i\geq 0\) with \(F_ 0=0\) and \(F_ 1=1\). If n is a natural number it is well known that n has a unique “Zeckendorf” representation of the form \(n=\sum^{N}_{i=0}d_ iF_ i\), where \(d_ i=0\) or \(d_ i=1\) and \(d_ id_{i+1}=0\) for all i, and where \(d_ 0=d_ 1=0\). If the Zeckendorf representation of m is given by \(m=\sum^{M}_{j=0}e_ jF_ j,\) then D. E. Knuth [Appl. Math. Lett. 1, No.1, 57-60 (1988; Zbl 0633.10011)] has defined the circle product of n and m by \(n\circ m=\sum^{N}_{i=0}\sum^{M}_{j=0}d_ ie_ jF_{i+j}\) and has proved that circle multiplication is an associative operation.
In the present paper the author establishes the associativity of circle multiplication by using an algebraic, as opposed to a combinatorial, argument. Thus, if Z is the set of finite sequences \((d_ 0,d_ 1,...,d_ n)\) where the \(d_ i\) are subject to the Zeckendorf restrictions given above, and \((d_ 0,d_ 1,...,d_ n)_ X=\sum^{n}_{i=0}d_ iX^ i,\) then circle multiplication corresponds to ordinary multiplication modulo the rule \(X^ i+X^{i+1}=X^{i+2}\). Since the author proves that any element of the ring \({\mathbb{Z}}[X]/<X^ 2- X-1>\) has at most one representation of the form \((d_ 0,d_ 1,...,d_ n)_ X\) and that the set of these representations is closed under multiplication, the associativity of circle multiplication follows immediately.
In the present paper the author establishes the associativity of circle multiplication by using an algebraic, as opposed to a combinatorial, argument. Thus, if Z is the set of finite sequences \((d_ 0,d_ 1,...,d_ n)\) where the \(d_ i\) are subject to the Zeckendorf restrictions given above, and \((d_ 0,d_ 1,...,d_ n)_ X=\sum^{n}_{i=0}d_ iX^ i,\) then circle multiplication corresponds to ordinary multiplication modulo the rule \(X^ i+X^{i+1}=X^{i+2}\). Since the author proves that any element of the ring \({\mathbb{Z}}[X]/<X^ 2- X-1>\) has at most one representation of the form \((d_ 0,d_ 1,...,d_ n)_ X\) and that the set of these representations is closed under multiplication, the associativity of circle multiplication follows immediately.
Reviewer: P.Hagis jun.
MSC:
11B39 | Fibonacci and Lucas numbers and polynomials and generalizations |
11A67 | Other number representations |
Keywords:
Fibonacci multiplication; Zeckendorf representation; associativity of circle multiplicationCitations:
Zbl 0633.10011Online Encyclopedia of Integer Sequences:
Array read by antidiagonals: T(n, k) = Knuth’s Fibonacci (or circle) product of n and k (”n o k”), n >= 1, k >= 1.Array read by antidiagonals: Arnoux’s product T(n,k) = n * k = nk + ceiling(phi n) ceiling(phi k), where phi = (1 + sqrt(5))/2 ; m, n >= 1.
A multiplication table for the rows of the extended Wythoff array. See comments for definition.
References:
[1] | Knuth, D. E., Fibonacci multiplication, Appl. Math. Lett., 1, 57-60 (1988) · Zbl 0633.10011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.