Some remarks about Fibonacci multiplication (Q922580): Difference between revisions

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 \textit{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.