Fibonacci multiplication (Q1095961): Difference between revisions

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.