Suppose that you have a large supply of red, white, green, and blue poker chips. You want to make a vertical stack of $n$ chips in such a way that the stack does not contain any consecutive blue chips.
(a) Find a recurrence relation for $a(n)$, where $a(n)$ denotes the number of ways you can make such a stack of $n$ poker chips.
(b) Solve the recurrence relation you found in part (a).
(c) Consider the specific case where you want to count only the stacks that use exactly $12$ chips. Count $a(12)$ directly. That is, count the cases with exactly $0$ blue chips, exactly $1$ blue chip, etc. and add up the cases to get an integer value for $a(12)$. Then check that your solution in part (b) gives the same answer.
I’ll give you a fairly detailed answer answer to this question, since it’s your first on this topic, and it takes a bit of practice or insight to come up with recurrence relations.
It’s often convenient temporarily to introduce some extra variables. Let $b(n)$ be the number of ‘legal’ stacks of $n$ chips with a blue chip on top, and let $c(n)=a(n)-b(n)$ be the number of ‘legal’ stacks of $n$ chips with a non-blue chip on top. To make a legal stack of $n+1$ chips, we can start with a legal stack of $n$ chips that has a blue chip on top and add a red, white, or green chip, or we can start with a legal stack of $n$ chips that does not have a blue chip on top and add a chip of any color. The first option produces $3b(n)$ legal stacks of $n+1$ chips, and the second produces $4c(n)$ legal stacks. (Why?) Thus, $a(n+1)=3b(n)+4c(n)$. Of course that’s not too helpful, since we really want $a(n+1)$ in terms of $a(n)$ (and maybe some $a(k)$’s with $k<n$). On the other hand, $3b(n)+4c(n)=3\big(b(n)+c(n)\big)+c(n)=3a(n)+c(n)$, so we can at least get rid of $b$: $$a(n+1)=3a(n)+c(n)\;.\tag{1}$$
Perhaps we should learn more about how $c$ is changing. If we repeat the reasoning that we used to get $a(n+1)=3b(n)+4c(n)$, we find that $$c(n+1)=3b(n)+3c(n)=3a(n)\;;\tag{2}$$
why?
And $(2)$ is equivalent to the recurrence $c(n)=3a(n-1)$, which we can substitute into $(1)$ to get
$$a(n+1)=3a(n)+3a(n-1)\;.\tag{3}$$
Now you need only determine the values of $a(0)$ and $a(1)$, and you’ll have both the recurrence $(3)$, valid for $n\ge 1$, and the right initial values. The rest of the problem is relatively mechanical.
It’s also possible to arrive at $(3)$ directly, without the use of any auxiliary variables; which you find easier is a matter of taste and practice. Suppose that you have a legal stack of $n+1$ chips. If it has a non-blue chip on top, it could have been obtained by adding that chip to any legal stack of $n$ chips, so there are $3a(n)$ legal stacks of $n+1$ chips with a non-blue chip on top. If the stack has a blue chip on top, however, it could not have been built by adding the blue chip to any old legal stack of $n$ chips, because some of those stacks already have a blue chip on top. However, it could have been built by adding a non-blue chip and then the blue chip to any legal stack of $n-1$ chips. Since there are three possible colors for the non-blue chip in this process, there are $3a(n-1)$ legal stacks of $n+1$ chips with a blue chip on top. Thus, $a(n+1)=3a(n)+3a(n-1)$.