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

It sounds very difficult but I think it actually is quite simple.

For a sequence of ternary digits (ie., use symbols 0, 1 and 2), you have the freedom to choose the first digit as you like, but for all the other digits, you can only choose the 2 alternatives you have.

So for n digits the number of sequences is:



Rewriting this as a recurrence relation:

If you have 5 stars, click 1 star or 2 or 3 or 4