# Sum and product of linear recurrences

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$?

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].$$

• For the sum $c_n = a_n + b_n$, I might be mistaken, but I thought we want the characteristic polynomial of $c_n$ to be $lcm\{ f_a(T), f_b(T) \}$? Oct 8, 2019 at 5:07
• Sure, the LCM works. I chose the product just because it is easier to write down. Oct 8, 2019 at 12:49
• I have two questions, (1) Why every solution to (*) is a linear combination of sequences $n\mapsto r^nn^k$, where r is a root of the characteristic polynomial? Isn't it only a linear combination of $n\mapsto r^n$? Dec 23, 2022 at 5:55
• (2) Yes, I agree that $c_n:=a_n+b_n$ is a linear combination of sequences of the form $r^nn^k$, but how does that show that $c_n$ is a linear recurrence sequence with the char polynomial given by the products? I can see that it is a linear recurrence sequence, but why should it have that char polynomial Dec 23, 2022 at 5:59
• I like this idea of using the resultant to produce a polynomial whose roots are the products of the roots of $f_a$ and $f_b$. What about multiplicities ? The resultant may have a multiplicity greater than required e.g. if there are several pairs of roots $\alpha, \beta$ with given product $\pi$ then rather than producing a polynomial with the least multiplicity $$\min_{\alpha\cdot\beta = \pi}\Big\{m_\alpha + m_\beta\Big\}$$ it will provide a characteristic equation with multiplicity $$\sum_{\alpha\cdot\beta = \pi}m_\alpha + m_\beta$$ Is there an algebraic way of producing the minimal one ? Mar 10 at 14:16