"Multiplication" of two linear recurrence relations 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?
 A: 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.$$
A: 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.
