Couldn't understand a step in solving Homogenous Linear Recurrence relations

Question

I was reading a Wiki on Brilliant.org regarding linear recurrence relations. They have mentioned that, "note that if two geometric series satisfy a recurrence, the sum of them also satisfies the recurrence".
And I am stuck there! How do can we prove the above statement formally? In addition to this how do we prove that $u_{n} = c_{1}u_{n-1}+...+c_{k}u_{n-k} \implies a_{n} = \alpha_{1}r_{1}^{n}+\alpha_{2}r_{2}^{n}$ .

Answer 1

It’s just a matter of checking the algebra. Suppose that the recurrence is

$$x_n=c_1x_{n-1}+c_2x_{n-2}+\ldots+c_kx_{n-k}\;,\tag{1}$$

and that $x_n=ar^n$ and $x_n=bs^n$ both satisfy it, meaning that

$$ar^n=c_1ar^{n-1}+c_2ar^{n-2}+\ldots+c_kar^{n-k}$$

and

$$bs^n=c_1bs^{n-1}+c_2bs^{n-2}+\ldots+c_kbs^{n-k}\;.$$

Let $u_n=ar^n+bs^n$. Then

$$\begin{align*} u_n&=ar^n+bs^n\\ &=(c_1ar^{n-1}+c_2ar^{n-2}+\ldots+c_kar^{n-k})+\\ &\quad+(c_1bs^{n-1}+c_2bs^{n-2}+\ldots+c_kbs^{n-k})\\ &=c_1(ar^{n-1}+bs^{n-1})+c_2(ar^{n-2}+bs^{n-2})+\ldots+c_k(ar^{n-k}+bs^{n-k})\\ &=c_1u_{n-1}+c_2u_{n-2}+\ldots+c_ku_{n-k}\;, \end{align*}$$

so the sequence $\langle u_n:n\in\Bbb N\rangle=\langle ar^n+bs^n:n\in\Bbb N\rangle$, the sum of the two geometric sequences, also satisfies the recurrence $(1)$.