Fibonacci multiplication
type: Item
instance of: scholarly article
title: Fibonacci multiplication
zbMATH Open document ID: 0633.10011
DOI: 10.1016/0893-9659(88)90176-0
author: Donald E. Knuth
published in: Applied Mathematics Letters
publication date: 1988-01-01T00:00:00Z
review text: The Fibonacci sequence \(\{F_ n\}\) is defined as follows: \(F_ 0=0\), \(F_ 1=1\), \(F_ k=F_{k-1}+F_{k-2}\) for \(k\geq 2\). A well-known theorem, due to Zeckendorf, states that every natural number has a unique representation as a sum of distinct Fibonacci numbers, if we stipulate that \(F_ 0\) and \(F_ 1\) are not used in the representation and that if \(F_ a\) and \(F_ b\) are used then \(| a-b| >1.\) If the Zeckendorf representations of m and n are \(m=F_{jq}+...+F_{j1}\) and \(n=F_{kr}+...+F_{k1}\), then the ``circle product'' of m and n is defined as follows: \(m\circ n=\sum^{q}_{b=1}\sum^{r}_{c=1}F_{jb+kc}.\) In particular, \(F_ j\circ F_ k=F_{j+k}\) if \(j\geq 2\) and \(k\geq 2\). It is proved in this paper that circle multiplication is an associative operation.
reviewed by: Peter Hagis jun.
Mathematics Subject Classification ID: 11B37
zbMATH DE Number: 4029663
zbMATH Keywords: Fibonacci numbers
zbMATH Keywords: Zeckendorf representations
zbMATH Keywords: circle product
zbMATH Keywords: associative operation
Wikidata QID: Q56502855
MaRDI profile type: Publication
full work available at URL: 0893-9659(88)90176-0
OpenAlex ID: W4212826062
cites work: Q5815665
cites work: A golden iterated map number system: Results and conjectures
cites work: Q5665234
cites work: Q5665263
description: scientific article; zbMATH DE number 4029663