How would I find the characteristic equation of this Recurrence Relation?

Question

Find and solve a recurrence relation for the number of $n$-digit ternary sequences with no consecutive digits being equal.

Since for ternary, meaning only $3$ possible entries for each space, e.g. $0$, $1$, $2$, the first slot $n$ has $3$ possible choices and then each position before ($n-1$, $n-2$, $\ldots$ , $2$, $1$) have $2$ choices each, I got the following recurrence relation:$$a_n=2\cdot a_{n-1}$$

Now I am trying to solve the homogeneous linear recurrence model, but I am stuck in finding a characteristic equation. How would I do this?

Answer 1

In the usual way...just assume that $a_n = A\cdot r^n$ therefore you have:

$$ a_n = 2a_{n-1} \rightarrow Ar^n = 2A\cdot r^{n - 1} = \frac{2A\cdot r^n}{r}\\ 1 = \frac{2}{r} \\ r = 2 $$

So $a_n = A\cdot2^n$ (which makes perfect sense since that recursion relation is clearly a simple exponential with common ratio of $2$).

Answer 2

Doubling every time should not require a characteristic equation! However, it is $x-2=0$.