Sum and product of linear recurrences

Question

Given $a_n = \alpha_1 a_{n-1} + \cdots + \alpha_k a_{n-k}$ and $b_n = \beta_1 b_{n-1} + \cdots + \beta_l b_{n-l}$ are linear recurrences with complex coefficients, how can I find linear recurrences for $a_n + b_n$ and $a_n b_n$?

Answer 1

It will be convenient to have all of the terms on the same side of the equation, so I will write your recurrence relation as $$ \tag{$\star$} a_n+\alpha_1a_{n-1}+\ldots+\alpha_k \,a_{n-k}=0, $$ and similarly for $b_n$.

The characteristic polynomial of the recurrence $(\star)$ is $T^k+\alpha_1 T^{k-1}+\ldots+\alpha_k$. Every solution to $(\star)$ is a linear combination of sequences $n\mapsto r^n n^k$, where $r$ is a root of the characteristic polynomial and $k$ is a non-negative integer that is smaller than the multiplicity of $r$. Let $f_a(T)$ and $f_b(T)$ be the characteristic polynomials of your two recurrences.

The sequence $c_n:=a_n+b_n$ is a linear combination of sequences of the form $r^n n^k$, where $r$ is a root of either $f_a(T)$ or $f_b(T)$. The roots of the product $f_a(T)f_b(T)$ are the roots of $f_a(T)$ and the roots of $f_b(T)$, so the sequence $a_n+b_n$ satisfies the recurrence whose characteristic polynomial is $f_a(T)f_b(T)$. Explicitly: $$ c_n+ (\alpha_1+\beta_1)c_{n-1} +(\alpha_2+\alpha_1\beta_1+\beta_2)c_{n-2}+\ldots+(\alpha_k\beta_\ell)c_{n-k-\ell}=0. $$

---

Let $d_n:=a_nb_n$. Then $d_n$ is a linear combination of terms $(r_1r_2)^n n^{k_1+k_2}$, where $r_1$ (resp. $r_2$) is a root of $f_a$ (resp. $f_b$) of multiplicity greater than $k_1$ (resp. $k_2$). So we need to find a polynomial whose roots are products of a root of $f_a$ times a root of $f_b$. One way to come up with such a polynomial is using the resultant.

The resultant $\mathrm{Res}_x(f(x),g(x))$ of two polynomials $f(x)$ and $g(x)$ is a quantity that depends polynomially on the coefficients of $f$ and $g$, which is $0$ if and only if $f$ and $g$ share a common root. The resultant can be computed as the determinant of the Sylvester matrix.

For $T$ a complex number, the polynomials $f_a(x)$ and $x^\ell f_b(T/x)$ share a common root if and only if $T$ is the product of a root of $f_a$ and a root of $f_b$. So $d_n$ satisfies the recurrence whose characteristic polynomial is $\mathrm{Res}_x(f_a(x),x^\ell f_b(T/x))$. Explicitly, this polynomial is $$ \mathrm{det}\left[\begin{array}{cccc} 1&\alpha_1&\alpha_2&\cdots&\alpha_k&0&0&\cdots&0\\ 0&1&\alpha_1&\cdots&\alpha_{k-1}&\alpha_k&0&\cdots&0\\ \vdots&&\ddots&&&&&&\vdots\\ 0&\cdots&0&1&\alpha_1&&&\cdots&\alpha_k\\ \beta_\ell&\beta_{\ell-1}T&\cdots&\beta_1 T^{\ell-1}&T^\ell&0&&\cdots&0\\ 0&\beta_\ell&\cdots&\beta_2 T^{\ell-1}&\beta_1 T^{\ell-1}&T^\ell&0&\cdots&0\\ \vdots&&\ddots&&&&&&\vdots\\ 0&\cdots&0&\beta_\ell&\beta_{\ell-1}T&&&\cdots&T^{\ell} \end{array}\right]. $$