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

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 01:37, 5 March 2024

scientific article
Language Label Description Also known as
English
Some remarks about Fibonacci multiplication
scientific article

    Statements

    Some remarks about Fibonacci multiplication (English)
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    Fibonacci multiplication
    0 references
    Zeckendorf representation
    0 references
    associativity of circle multiplication
    0 references

    Identifiers