# Sum of two recursive sequences as a recursive sequence

Suppose I have two sequences $x_n$ and $y_n$ defined by:

$$x_n = a_1 x_{n-1} + a_2 x_{n-2} + ... = \sum_{p=1}^{N_x} a_p x_{n-p}$$

and

$$y_n = b_1 y_{n-1} + b_2 y_{n-2} + ... = \sum_{p=1}^{N_y} b_p y_{n-p}$$

Now let $z_n = x_n + y_n$.

Is there a way to derive a finite set of $c_p$ values so that:

$$z_n = c_1 z_{n-1} + c_2 z_{n-2} + ... = \sum_{p=1}^{N_z} c_p z_{n-p}$$

All values are real.

Thanks,

Ced

Followup:

Thank you, Delta-u. This is precisely the slick trick I was looking for. Your notation threw me off a little bit, as did your reversing of the subscripts in your summation. I really appreciate that this solution is easily extensible to more than two constituent sequences.

I changed it to this:

$$P_x=S^{N_x} -\sum_{p=1}^{N_x} a_{p} S^{N_x-p}$$

Confirmation of the $N_x=1$, $N_y=1$ case:

$$x_n = a_{1} x_{n-1}$$ $$y_n = b_{1} y_{n-1}$$

Which solve to:

$$x_n = a_{1}^n x_0$$ $$y_n = b_{1}^n y_0$$

\begin{aligned} x_n + y_n &= a_{1}^n x_0 + b_{1}^n y_0 \\ &= ( a_{1}^{n-1} x_0 + b_{1}^{n-1} y_0 )(a_{1}+b_{1}) - [b_{1} a_{1}^{n-1} x_0 + a_{1} b_{1}^{n-1} y_0 ] \\ &= ( x_{n-1} + y_{n-1} )(a_{1}+b_{1}) - [ a_{1}^{n-2} x_0 + b_{1}^{n-2} y_0 ]a_{1}b_{1} \\ &= ( x_{n-1} + y_{n-1} )(a_{1}+b_{1}) - [ x_{n-2} + y_{n-2} ]a_{1}b_{1} \end{aligned}

Which is in the form of:

$$z_n = (a_{1}+b_{1}) z_{n-1} - a_{1}b_{1} z_{n-2}$$

The polynomial approach:

$$P_x: S - a_{1}$$ $$P_y: S - b_{1}$$ $$P_z: ( S - a_{1} )( S - b_{1} ) = S^2 - (a_{1}+b_{1}) S + a_{1}b_{1}$$

$$c_{1} = (a_{1}+b_{1})$$ $$c_{2} = -a_{1}b_{1}$$

## 1 Answer

Yes it is possible. Let $E$ the set of sequences and consider the shift operator: $$S:E \to E, \, (u_n)_{n \in \Bbb N} \mapsto (u_{n+1})_{n \in \Bbb N}$$ then $x=(x_n)_{n \in \Bbb N}$ satisfies the recursion means that: $$P(S) x=0$$ where $P=X^{N_x} +\sum_{p=0}^{N_x-1} a_{N_x-p} X^p$.

Notice that if $\tilde{P}$ is a polynomial such that $P| \tilde{P}$ then $\tilde{P}(S)x=0$.

Similarly the relation for $y$ can be written as: $$Q(S) y=0$$

Let $R=\operatorname{lcm}(P,Q)$ (or any polynomial divisible by both $P$ and $Q$).

Then:: $$R(S)(x+y)=R(s)x+R(s)y=0+0=0$$

So $z=x+y$ satisfies a such a relation with $R$.

All it remains is to computer a least common divisor of two polynomials.