Hadamard product of linear recurrences with umbral calculus

Question

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

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.