Let $R$ be a ring, $d_0, d_1, d_2, \dots \in R$ and $e_0, e_1, e_2, \dots \in R$ be linear recurrence sequences, such that

  • $d_m = a_1 d_{m-1} + a_2 d_{m-2} + \dots + a_k d_{m-k}$ for $m \geq k$,
  • $e_m = b_1 e_{m-1} + b_2 e_{m-2} + \dots + b_l e_{m-l}$ for $m \geq l$.

It is possible to analyze their joint properties with the linear functional $T: R[d, e] \to R$ such that

$$ T(d^i e^j) = d_i e_j. $$

One can show that $T(f(d, e))=0$ whenever $f(d, e)$ lies in the ideal $\langle a(d), b(e) \rangle$, where

  • $a(x) = x^k - a_1 x^{k-1} - a_2 x^{k-2} - \dots - a_k$,
  • $b(x) = x^l - b_1 x^{l-1} - b_2 x^{l-2} - \dots - b_l$

are the characteristic polynomials of the sequences $d_i$ and $e_j$.

Composed sum

As an example, let $f_0, f_1, f_2, \dots \in R$ be a sequence such that $f_k = \sum\limits_{i=0}^k \binom{k}{i}d_i e_{k-i}$. Let $f=d+e$, one can see that

  • $T(f^k)=T((d+e)^k) = T\left(\sum\limits_{i=0}^k \binom{k}{i} d^i e^{k-i}\right) = \sum\limits_{i=0}^k \binom{k}{i} T(d^ie^{k-i}) = f_k$.

To show that $f_k$ is a linear recurrence obeying to the rule

  • $f_m = c_1 f_{m-1} + c_2 f_{m-2} + \dots + c_t f_{m-t}$ for $m \geq t$,

it is sufficient to show that there is a polynomial function $c(f)$ such that $c(f) \in \langle a(d), b(e) \rangle$.

This function exists and can be given explicitly as

  • $c(d+e) = \prod\limits_{i=1}^k \prod\limits_{j=1}^l ((d+e)-(\lambda_i + \mu_j)),$

where $a(d) = \prod\limits_{i=1}^k (d-\lambda_i)$ and $b(e) = \prod\limits_{j=1}^l (e-\mu_j)$. The fact that $c(d+e) \in \langle a(d), b(e) \rangle$ is proven as follows:

  • $c(d+e) = \prod\limits_{i=1}^k \prod_{j=1}^l ((d-\lambda_i)+(e-\mu_j)) = \sum\limits_{d_{ij} \in \{0,1\}} \prod\limits_{i=1}^k \prod\limits_{j=1}^l(d-\lambda_i)^{d_{ij}}(e-\mu_j)^{1-d_{ij}}$

In the sum above, there are $2^{kl}$ summands, each of them is divisible by either $a(d)$ or $b(e)$, so $c(d+e) \in \langle a(d), b(e)\rangle$.

Composed product (question)

Now the question is, how to prove that $f_k = d_k e_k$ is a linear recurrence?

Using similar logic as above, one would define $f = de$ and then look for $c(f) \in \langle a(d), b(e) \rangle$. I assume that

  • $c(de) = \prod\limits_{i=1}^k \prod\limits_{j=1}^l (de - \lambda_i \mu_j)$

would suffice, but I don't see any simple way to prove it in a similar manner with $c(d+e)$.

Another question that I have is whether

  • $c(d \diamond e) = \prod\limits_{i=1}^k \prod\limits_{j=1}^l (d \diamond e - \lambda_i \diamond \mu_j)$

would lie in $\langle a(d), b(e) \rangle$ for somewhat arbitrary meaningful operation $\diamond$?

  • $\begingroup$ Are the $c_i$ and $e_i$ of the 1st paragraph supposed to be the same? $\endgroup$ Commented May 23, 2022 at 3:53
  • 1
    $\begingroup$ Oops, that was a typo. Fixed now, thanks! $\endgroup$ Commented May 23, 2022 at 8:29
  • $\begingroup$ Yes, thanks for pointing out! $\endgroup$ Commented May 23, 2022 at 10:40

1 Answer 1


Ok, I think I figured it out. For $k=l=1$ we have

$$ c(de) = de - \lambda \mu = de - d\mu + d\mu - \lambda \mu = d(e - \mu) + (d - \lambda) \mu. $$

Rewriting it in the same way for arbitrary $k$ and $l$, we get

$$\begin{align} c(de) = & \prod\limits_{i=1}^k \prod\limits_{j=1}^l (d(e-\mu_j) + (d - \lambda_i )\mu_j) = \\ = \sum\limits_{r_{ij} \in \{0,1\}} & \prod\limits_{i=1}^k \prod\limits_{j=1}^l d^{r_{ij}}\mu_j^{1-r_{ij}}(e-\mu_j)^{r_{ij}}(d-\lambda_i)^{1-r_{ij}}. \end{align}$$

Then the same logic applies as to $c(d+e)$ in the question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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