2
$\begingroup$

I was going through the book "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the proof the following theorem. The backward proof is fine but I did not feel the forward proof of quite satisfactory.

Theorem: Let $c_1$ and $c_2$ be real numbers. Suppose that $r^{2} − c_1r−c_2=0$ has two distinct roots $r_1$ and $r_2$ . Then the sequence $\{a_n\}$ is a solution of the recurrence relation $a_n = c_1 a_{n−1} + c_2 a_{n−2}$ if and only if $a_n =α_1r^{n} +α_2r^{n}$ for $n = 0, 1, 2,...,$ where $α_1$ and $α_2$ are constants.

Proof: We must do two things to prove the theorem. First, it must be shown that if $r_1$ and $r_2$ are the roots of the characteristic equation, and $α_1$ and $α_2$ are constants, then the sequence $\{a_n\}$ with $a_n =α_1r^{n} +α_2r^{n}$ is a solution of the recurrence relation. Second, it must be shown that if the sequence $\{a_n \}$ is a solution, then $a_n = c_1 a_{n−1} + c_2 a_{n−2}$ for some constants $α_1$ and $α_2$.

The forward proof

Now we will show that if $a_n =α_1r^{n} +α_2r^{n}$ , then the sequence $\{a_n\}$ is a solution of the recurrence relation. Because $r_1$ and $r_2$ are roots of $r^{2} − c_1r−c_2=0$ ,it follows that $r_1^{2}=c_1r_1+c_2$,$r_2^{2}=c_1r_2+c_2$. From these equations, we see that

$$c_1a_{n−1} + c_2a_{n−2}$$

$$= c_1(α_1r_1^{n−1}+α_2r_2^{n−1} )+c_2(α_1r_1^{n−2}+α_2r_2^{n−2})$$ $$ = α_1r_1^ {n−2}(c_1r_1+c_2)+α_2r_2 ^{n−2}(c_1r_2 + c_2)$$ $$ = α_1r_1^{n−2}r_1^{2}+α_2r_2^{n−2}r_2^{2}$$ $$ = α_1r_1^{n} +α_2r_2{n}$$ $$ = a_n.$$

This shows that the sequence $\{a_n\}$ with $a_n = α_1 r_1^{n}+α_2r_2^{n}$ is a solution of the recurrence relation.

The backward proof

To show that every solution $\{a_n\}$ of the recurrence relation $a_n = c_1 a_{n−1} + c_2 a_{n−2}$ has $a_n =α_1r^{n} +α_2r^{n}$ for $n = 0, 1, 2,...$ , for some constants $α_1$ and $α_2$, suppose that $\{a_n\}$ is a solution of the recurrence relation, and the initial conditions $a_0 = C_0$ and $a_1 = C_1$ hold. It will be shown that there are constants $α_1$ and $α_2$ such that the sequence $\{a_n\}$ with $a_n =α_1r^{n} +α_2r^{n}$ satisfies these same initial conditions.

This requires that

$a_0=C_0=α_1+α_2$, $a_1=C_1=α_1r_1+α_2r_2$.

We can solve these two equations for α_1 and α_2 . From the first equation it follows that

$α_2 = C_0 − α_1$ .

Inserting this expression into the second equation gives

$C_1=α_1r_1+(C_0−α_1)r_2$.

Hence,

$C_1=α_1(r_1 −r_2)+C_0r_2$.

This shows that

$α_1=\frac{ C_1 − C_0r_2}{r_1−r_2}$

and

$α_2=C_0−α_1=C_0− \frac{C_1 − C_0r_2} {r_1−r_2} = \frac{C_0r_1 − C_1}{ r1−r2}$

, where these expressions for $α_1$ and $α_2$ depend on the fact that $r_1 \neq r_2$ . (When $r_1 = r_2$ , this theorem is not true.) Hence, with these values for $α_1$ and $α_2$ , the sequence $\{a_n\}$ with $a_n =α_1r^{n} +α_2r^{n}$ satisfies the two initial conditions. We know that $\{a_n\}$ and $\{α_1r^{n} +α_2r^{n}\}$ are both solutions of the recurrence relation $a_n = c_1 a_{n−1} + c_2 a_{n−2}$ and both satisfy the initial conditions when $n = 0$ and $n = 1$. Because there is a unique solution of a linear homogeneous recurrence relation of degree two with two initial conditions, it follows that the two solutions are the same, that is, $a_n =α_1r^{n} +α_2r^{n}$ for all nonnegative integers $n$.


Doubts

In the forward part we are supposed to prove something of the form,

if "$\{a_n\}$ is a solution of the recurrence relation" $=>$ "$\{a_n\}$ is same as $\{α_1r^{n} +α_2r^{n}\}$".


Here in the above forward proof, for the purpose below,

It will be shown that there are constants $α_1$ and $α_2$ such that the sequence $\{a_n\}$ with $a_n =α_1r^{n} +α_2r^{n}$ satisfies these same initial conditions.

we are sort of using the conclusion of the above implication to show the conclusion is true if the hypothesis is true.


We know that $\{a_n\}$ and $\{α_1r^{n} +α_2r^{n}\}$ are both solutions of the recurrence relation $a_n = c_1 a_{n−1} + c_2 a_{n−2}$

I hope they are using the proof of the first part (backward proof) to say that $\{α_1r^{n} +α_2r^{n}\}$ is a solution of the recurrence relation.


Because there is a unique solution of a linear homogeneous recurrence relation of degree two with two initial conditions

I hope the above is theorem which exists and it is not dealt with in the book.


The entire forward proof for seems a bit weird to me and it seems that was sort of forcely made to agree the facts of mathematics.

$\endgroup$
1

1 Answer 1

3
$\begingroup$

Alternative proof: Let $U$ be the set of sequences and $A_m : U \mapsto \mathbb{R}$ be defined as $$A_m((u_n)_n) := u_{m+2} -c_1 u_{m+1} - c_2 u_m.$$ Then it is easy to check that A_m is linear. One also checks that $(r_i^n)_n$ satisfies $A_m((r_i^n)_n) = 0$ for all $m \ge 0$ and $i= 1,2$. It follows that $A_m((\alpha_1 r_1^n + \alpha_2 r_2^n)_n) = 0$ for all $m \ge 0$.

One obtains uniqueness of solutions if $u_0 = C_0$ and $u_1 = C_1$ by contradiction: suppose there were two solutions $(u_n)_n$ and $(v_n)_n$. Let $m$ be the smallest number such that $u_m \neq v_m$. The recurrence relation leads to a contradiction.

Now suppose $C_0$ and $C_1$ are given. We must check that there are $\alpha_1$ and $\alpha_2$ such that $$ \alpha_1 r_1^0 + \alpha_2 r_2^0 = C_0$$ and $$ \alpha_1 r_1^1 + \alpha_2 r_2^1 = C_1$$. Such $alpha_i$ can be found if the determinant of the matrix of the system is nonzero. One computes the determinant: $r_2 - r_1 \neq 0$ since $r_1 \neq r_2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .