6

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

nasosev
  • 469

1 Answers1

9

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

Julian Rosen
  • 16,142
  • 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) }$? – Michael Wehar Oct 08 '19 at 05:07
  • Sure, the LCM works. I chose the product just because it is easier to write down. – Julian Rosen Oct 08 '19 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$? – dragoboy Dec 23 '22 at 05: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 – dragoboy Dec 23 '22 at 05: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 ? – Olivier Bégassat Mar 10 '23 at 14:16
  • Is there an algebraic way in line with the resultant you used (as opposed to just defining the polynomial through roots and multiplicities) to construct the polynomial with roots the products of the roots of $f_a$ and $f_b$ and multiplicities the minimum above, so that the linear span of the products of sequences satisfying $f_a$ and $f_b$ is precisely the space of linear recurrent sequences satisfying this recursive relation ? – Olivier Bégassat Mar 10 '23 at 14:19
  • @OlivierBégassat It's an interesting question. I worked out a method to compute the minimal characteristic polynomial that is algebraic in the sense that it only involves arithmetic in the field generated by the coefficients of recurrence relations we started with, rather than needing do work with roots of polynomials. One note: I believe the multiplicity of $\pi$ in the desired recurrence relation should by $\max_{\alpha\beta=\pi} {m_{\alpha} + m_{\beta} - 1}$. – Julian Rosen Mar 12 '23 at 22:01
  • (cont.) First, observe that the gcd of two polynomials can be computed algebraically using the Euclidean algorithm, and the radical of a polynomial (= polynomial with the same set of roots but no repeated roots) is $Rad(f) = f / gcd(f, f')$. Recursively define two sequences of polynomials $f_m$ and $r_m$. The initial values are $f_1=Rad(f) / Rad(gcd(f,f'))$ and $r_1=f/f_1$. For $m\geq 2$, define $f_m = Rad(r_{m-1}) / Rad(gcd(r_{m-1}, r_{m-1}^{(m)})$ and $r_m = f_{m-1}/f_m^m$ (the superscript $r^{(m)}$ denotes $m$-th order derivative). – Julian Rosen Mar 12 '23 at 22:02
  • (cont.) These sequences satisfy $f_m=r_m=1$ when $m$ is sufficiently large (say $m>M$). You can check that the $f_m$ are square-free, pairwise coprime, and $f=f_1\cdot f_2^2\cdot \ldots\cdot f_M^M$. In other words, $f_m$ is the product of the roots of $f$ that have multiplicity exactly $m$. In a similar way, we can find $g_1,\ldots,g_M$ such that $g = g_1\cdot g_2^2\cdot\ldots\cdots g_M^M$. – Julian Rosen Mar 12 '23 at 22:02
  • (cont.) Now, the $lcm$ of two polynomials can also be computed without leaving the base field. The $lcm$ of the polynomials $Rad(Res(f_i, g_j))^{i+j-1}$ for $1\leq i,j\leq M$, should be the desired minimal characteristic polynomial.

    It's possible I made a mistake here, but it seems an approach like this work anyhow.

     – Julian Rosen Mar 12 '23 at 22:04
  • I thought some more about it, and there's another way to compute the minimal polynomial without having to extract roots. For $0\leq i< deg(f)$, let $c_{i,n}$ be the sequence satisfying the recurrence given by $f$, along with $c_{i,n} = \delta_{i,n}$ for $0\leq n<deg(f)$, and similarly $d_{j,n}$ for $0\leq j<deg(g)$. For fixed $i$ and $j$, we can start writing out the vectors $(c_{i,m}d_{j,m},c_{i,m+1}d_{j,m+1},\ldots,c_{i,m+deg(f)deg(g)}d_{j,m+deg(f)deg(f)})$ for $m=0,1,2,\ldots$. – Julian Rosen Mar 12 '23 at 23:26
  • Once the list of vectors first becomes linearly dependent, we can read off the coefficients of the characteristic polynomial of the sequence $n\mapsto c_{i,n}d_{j,n}$ as the coefficients of the linear relation we find. Now, repeat for all $i$ and $j$ (a finite computation), and take the lcm of the polynomials produced this way (also a finite computation). None of this involved explicitly working with the roots of $f$ or $g$. – Julian Rosen Mar 12 '23 at 23:27