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


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

  • $\begingroup$ 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) \}$? $\endgroup$ Oct 8, 2019 at 5:07
  • $\begingroup$ Sure, the LCM works. I chose the product just because it is easier to write down. $\endgroup$ Oct 8, 2019 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.