3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.