We have a path of size $N$ and $1\times1$ blocks of $4$ colors: yellow, red, blue and white. We need to fill the path with blocks but we cannot have $2$ blocks of the same color in a row (we can have $2$ white blocks in a row only, but not $2$ yellow $2$ red or $2$ blue). I need to find the recurrence relation for this problem. (The question is how many different ways do we have to fill the path with these blocks)
How I started:
We can fill the first space with any of the $4$ options - $4f(n-1)$ We can fill the second place for sure with $3$ blocks if the first color was non-white and $4$ blocks if the first color was white. And this is where I am stuck.
$\begin{align} f(1) &= 4\\ f(2) &= 13\\ \end{align}$
Here’s one approach. I’ll describe it in some detail, since you can use similar ideas to analyze many similar problems.
Let $a_n$ be the number of ways to fill a path of length $n$, and let $b_n$ be the number of those ways that end in a white block. Suppose that we’ve filled a path of length $n$; in how many ways can we extend it to a path of length $n+1$?
If the path of length $n$ ends in a white block, we can add a block of any color, so there are $4$ ways to extend it. Since there are $b_n$ paths of length $n$ that end in a white block, this accounts for $4b_n$ paths of length $n+1$.
If the path of length $n$ ends in a non-white block, we can add a block of any color except the color of the last block, so there are $3$ ways to extend it. There are $a_n-b_n$ paths of length $n$ that end in a non-white block, so this accounts for another $3(a_n-b_n)$ paths of length $n+1$.
These are the only possibilities, so
$$a_{n+1}=4b_n+3(a_n-b_n)=3a_n+b_n\;.$$
But we want to express $a_{n+1}$ only in terms of $a_n,a_{n-1}$, etc., so we have to get rid of $b_n$ somehow. One way is to find a companion recurrence for $b_{n+1}$. How many paths of length $n+1$ ending in a white block did we just create? That’s easy: every path of length $n$ can be extended by a white block, so $b_{n+1}=a_n$. Of course that means that $b_n=a_{n-1}$, and hence
$$a_{n+1}=3a_n+a_{n-1}$$
or, if you prefer,
$$a_n=3a_{n-1}+a_{n-2}\;.$$
Now you just need two initial values to get the recurrence off the ground. There is one way to fill the path of length $0$ — use no blocks! — and as you say, there are $4$ ways to fill a path of length $1$, so $a_0=1$ and $a_1=4$.