Understanding Linear Recurrence Theorem

Question

I have been trying to understand this theorem but I could not get past a point. The proof has been taken from Kenneth Rosen's Discrete Mathematics.

THEOREM 1: Let c₁ and c₂ be real numbers. Suppose that r² − c₁r − c₂ = 0 has two distinct roots r₁ and r₂. Then the sequence {a_n} is a solution of the recurrence relation a_n = α₁ a_n−1 + α₂ a_n−2 if and only if a_n =α₁ r₁ⁿ +α₂ r₂ⁿ for n=0,1,2,...,where α₁ and α₂ are constants.

PROOF : We must do two things to prove the theorem. First, it must be shown that if r₁ and r₂ are the roots of the characteristic equation, and α₁ and α₂ are constants, then the sequence {a_n} with a_n = α₁r₁ⁿ + α₂r₂ⁿ is a solution of the recurrence relation. Second, it must be shown that if the sequence {a_n} is a solution, then a_n = α₁r₁ⁿ + α₂r₂ⁿ for some constants α₁ and α₂.

Now we will show that if a_n = α₁r₁ⁿ + α₂r₂ⁿ, then the sequence {a_n} is a solution of the recurrence relation.Because r₁ and r₂ are roots of r² − c₁r − c₂ = 0, it follows that r₁² = c₁r₁ +c₂, r₂² =c₁r₂ +c₂.

Now until this part what I have understood(if I am right) that they have just taken a quadratic equation and split it into its roots.

Now the following algebraic part did not make any sense to me. I want to understand this part:

c₁a_n−1 + c₂a_n−2 = c₁(α₁r₁ⁿ⁻¹ + α₂r₂ⁿ⁻¹) + c₂(α₁r₁ⁿ⁻² + α₂r₂ⁿ⁻²)

= α₁r₁ⁿ⁻²(c₁r₁ + c₂) + α₂r₂ⁿ⁻²(c₁r₂ + c₂)

= α₁r₁ⁿ⁻²r₁² + α₂r₂ⁿ⁻²r₂²

= α₁ r₁ⁿ + α₂ r₂ⁿ

= a_n.

This shows that the sequence {a_n} with a_n = α₁r₁ⁿ + α₂r₂ⁿ is a solution of the recurrence relation.

Now I have omitted rest of the proof because I could no get past this point. If someone requires it I can edit it. or If someone can explain further part in simple english I would be very grateful for that. But for now I just want to understand the above part.

Answer 1

Solutions to linear recurrence relations started making a lot more sense to me once I found a source that tied it to linear algebra. I won't spell out all of the details, but "the interested reader" can verify most of it.

---

Consider $\mathbb R^\mathbb N$, the linear space of real sequences with termwise addition and termwise scalar multiplication. The key idea is that the set of all real sequences that satisfy a linear recurrence relation is a subspace of $\mathbb R^\mathbb N$. You can check for yourself that if $(a_n)$ and $(b_n)$ satisfy $f_n=\alpha f_{n-1}+\beta f_{n-2}$ then so do $(c:n\mapsto a_n+b_n)$ and $(d:n\mapsto ka_n)$.

$$c_n=a_n+b_n=(\alpha a_{n-1}+\beta a_{n-2})+(\alpha b_{n-1}+\beta b_{n-2})\\=\alpha (a_{n-1}+b_{n-1})+\beta(a_{n-2}+b_{n-2})=(\alpha c_{n-1}+\beta c_{n-2})$$

$$d_n=ka_n=k(\alpha a_{n-1}+\beta a_{n-2})=\alpha ka_{n-1}+\beta ka_{n-2}=(\alpha d_{n-1}+\beta d_{n-2})$$

So, since being a solution to a linear recurrence relation is preserved by addition and scalar multiplication, the set of all solutions is a subspace of all real sequences. Since an $n$'th degree linear recurrence relation is defined by assigning the first $n$ terms of the sequence, it stands to reason that the dimension of the subspace is $n$. Now we are just left with finding a basis for the subspace.

---

So assume that $(n\mapsto r^n)$ for some real non-zero $r$ satisfies the recurrence relation. Then $$r^n=\alpha r^{n-1}+\beta r^{n-2}\\r^2=\alpha r+\beta\\ r^2-\alpha r-\beta=0\\$$

Long story short, for a two-term linear recurrence relation whose characteristic polynomial has distinct roots, a basis for the subspace of solutions $(n\mapsto r^n_1)$ and $(n\mapsto r^n_2)$, where $r_1$ and $r_2$ are the roots of the characteristic polynomial. Therefore, the set of all solutions is the linear combinations of those two basis solutions.