"Multiplication" of two linear recurrence relations

Question

Array $a_n$ is defined as:

$$a_0 = 1, \quad a_{n+1} = k_{a1}a_{n} + k_{a0}$$

Array $b_n$ is defined as:

$$b_0 = 1, \quad b_{n+1} = k_{b1}b_{n} + k_{b0}$$

Array $c_n$ is defined as:

$$c_n = a_{n}b_{n}$$

($k_{a1}$, $k_{a0}$, $k_{b1}$, $k_{b0}$ are some constants)

I suspect (but may be wrong) that $c_n$ would have to satisfy a linear recurrent relation involving only elements of itself, but of higher degree than recurrences for $a_n$ and $b_n$. Is it possible to derive such recurrent relation in this (or similar) form:

$$c_0 = 1, c_1 = (k_{a1}+k_{a0})(k_{b1}+k_{b0}), \quad c_{n+2} = k_{c2}c_{n+1} + k_{c1}c_{n} + k_{c0}$$

with $k_{c2}$, $k_{c1}$, $k_{c0}$ expressed as functions of $k_{a1}$, $k_{a0}$, $k_{b1}$, $k_{b0}$?

Or, maybe I am wrong, and such recurrence relation does not exist?

Answer 1

Recursions of degree $3$ are necessary (and probably sufficient), for example, if $$a_0=b_0=1,\qquad a_{n+1}=ua_n+1,\qquad b_{n+1}=vb_n+1,$$ then (I believe that) the sequence $c_n=a_nb_n$ solves the recursion $$ c_{n+3}=(uv+u+v)c_{n+2}-uv(u+v+1)c_{n+1}+u^2v^2c_n+1-uv.$$

Answer 2

Use generating functions, define $A(z) = \sum_{n \ge 0} a_n z^n$ and similarly $B(z)$. Multiply your recurrences by $z^n$ and add over $n \ge 0$, recognize e.g. $\sum_{n \ge 0} a_{n + 1} z^n = (A(z) - a_0)/z$ and get:

$\begin{align} \frac{A(z) - 1}{z} &= k_{a 1} A(z) + \frac{k_{a 2}}{1 - z} \\ \frac{B(z) - 1}{z} &= k_{b 1} B(z) + \frac{k_{b 2}}{1 - z} \end{align}$

Solutions are:

$\begin{align} A(z) &= \frac{1 + (k_{a 2} - 1) z}{1 - (k_{a 1} + 1) z + k_{a 1} z^2} \\ B(z) &= \frac{1 + (k_{b 2} - 1) z}{1 - (k_{b 1} + 1) z + k_{b 1} z^2} \end{align}$

Splitting into partial fractions allows to get the terms $a_n$ and $b_n$ from the resulting geometric series, either in the form $a_n = r_{a 1} \alpha_a^n + r_{a 2} \beta_a^n$ (denominator has different zeros) or $a_n = s_{a 1} \alpha_a^n + s_{a 2} n \alpha_a^n$ (denominator is a square), similarly for $b_n$. In any case, your $c_n = a_n b_n$ will be the product of the above. Assuming all zeros of the denominators distinct, you have something like:

$$ c_n = r_{c 1} (\alpha_a \alpha_b)^n + r_{c 2} (\alpha_a \beta_b)^n + r_{c 3} (\beta_a \alpha_b)^n + r_{c 4} (\beta_a \beta_b)^n $$

(If zeros repeat in a denominator, change e.g. $\beta_a \mapsto n \alpha_a$; if zeros repeat among denominators you get less terms). This is the solution to a homogeneous linear recurrence of order (at most) 4 with constant coefficients. Using the same process as above backwards you can derive this recurrence. Yes, it is a mess.