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



Hadamard product of linear recurrences with umbral calculus
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.


