Is it a solution of the recurrence relation?

Question

I am given a recurrence relation such that $a_n = 2a_{n-1} - a_{n-2}$ for $n = 2, 3, 4...$

I am to test whether $a_n = 2^n$ is a solution to the recurrence relation.

I am new to this, but it seems like there are two ways of doing this.

Given the first few terms in the sequence $2^n$, we might have $1,2, 4, 8, 16 ... $

Then we can ask, is it true that $4 = 2*2 - 1$? Of course not.

This is verified by another method.

Algebraically, if it were true that this was a solution to the recurrence relation, we could write: $2(2^{n-1}) - 2^{n-2} = 2^n$

Simplifying, we get:

$2^n - 2^{n-2} = 2^n$. Of course, this is mistaken.

So we have shown, by two separate methods, that $a_n = 2^n$ is not a solution to the recurrence relation.

Is this sufficient for proving that it is not a solution? Is one method better than the other?

Answer 1

Note that $a_n = 2a_{n-1} - a_{n-2} \implies a_n-a_{n-1}=a_{n-1}-a_{n-2}$

Answer 2

The characteristic equation of the the given recursive relation is $$r^2=2r-1$$ which it has the double root $r=1$ so we have $$a_n=\alpha n+\beta$$