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?
Best Answer
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.$$