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} $$
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.