# Hadamard product of linear recurrences with umbral calculus

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

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

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.