Some remarks about Fibonacci multiplication
type: Item
instance of: scholarly article
title: Some remarks about Fibonacci multiplication
zbMATH Open document ID: 0711.11008
DOI: 10.1016/0893-9659(89)90078-5
author: Pierre Arnoux
published in: Applied Mathematics Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11B39
Mathematics Subject Classification ID: 11A67
zbMATH DE Number: 4168761
zbMATH Keywords: Fibonacci multiplication
zbMATH Keywords: Zeckendorf representation
zbMATH Keywords: associativity of circle multiplication
reviewed by: Peter Hagis jun.
MaRDI profile type: Publication
full work available at URL: 0893-9659(89)90078-5
OpenAlex ID: W2047242165
cites work: Fibonacci multiplication
Recommended article: Fibonacci multiplication
Recommended article: Associativity of recurrence multiplication
Recommended article: Généralisation de la multiplication de Fibonacci. (Generalization of the Fibonacci multiplication)
Recommended article: Fibonacci with a Golden Ring
Recommended article: Q4839853
Recommended article: Tribonacci multiplication
Recommended article: Q5696251
Recommended article: Q4206803
Recommended article: Q4519622
description: scientific article; zbMATH DE number 4168761