Associativity of recurrence multiplication (Q1334832)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Associativity of recurrence multiplication |
scientific article |
Statements
Associativity of recurrence multiplication (English)
0 references
22 September 1994
0 references
Let \(G_ k\) be the recurring sequence satisfying the recurrence \(G_{k+d} = a_ 1 G_{k+d-1} + \cdots + a_ dG_ k\) with initial values \(G_ k = a_ 1G_{k-1} + a_ 2G_{k-2} + \cdots + a_ k G_ 0 + 1\) for \(k = 0, \dots, d - 1\) and the additional condition \(a_ 1 \geq a_ 2 \geq \cdots \geq a_ d > 0\). There is a unique digital representation of every integer \(m\) in the form \(M = \sum^ L_{\ell = 0} e_ lG_ l\) where the digits are restricted by a certain lexicographic condition. For two positive integers \(m\) and \(n\) given in \(G\)-ary representation \(m = \sum^ L_{\ell = 0} e_ lG_ l\) and \(n = \sum^ K_{k = 0} d_ kG_ k\), the ``circle multiplication with shift \(s\)'' is defined to be the following binary operation: \[ m \circ_ sn : = \sum^ L_{\ell = 0} \sum^ K_{k = 0} e_ \ell d_ k G_{k+ \ell + s}. \] This generalizes Knuth's Fibonacci multiplication. It is shown that for all sufficiently large \(s\), the circle product \(\circ_ s\) is associative.
0 references
associativity
0 references
linear recurrences
0 references
digit expansions
0 references
circle multiplication with shift
0 references