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
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    associativity
    0 references
    linear recurrences
    0 references
    digit expansions
    0 references
    circle multiplication with shift
    0 references
    0 references