Problem: Find the number of ways we can paint the fence containing n vertical pickets with 4 different colors. The problem is that, before we start painting, we adjust the buckets of colors in one row. Each time we paint a picket, the next picket can only be painted with colors from the neighbor buckets.
Example: If we have colors red blue green yellow, and we start painting with blue, the next picket can only be painted with red or green.
How I tried solving the problem I tried counting the overall possible ways to paint the fence via stars and bars method using theorem two $$\binom{n+k-1}{k-1}$$ where n is the number of pickets and k is number of paints and then dividing the result by 2.
The correct answer: We have to use the following recurrence relation to solve this problem: $$f(n) = f(n-1) + f(n-2)$$ Why do we need to do this? Can someone explain how we came to this answer?
There are basically two states you can be in: Either you just used one of the two outer colours, or you just used one of the two inner colours. If you used one of the outer colours, you now need to use the neighbouring inner colour; whereas if you used one of the inner colours, you can now either use the other inner colour, or the neighbouring outer colour. Thus, if we count the ways of painting $n$ pickets and ending up with an inner or outer colour by $a_n$ and $b_n$, respectively, we have $a_n=a_{n-1}+b_{n-1}$ and $b_n=a_{n-1}$. Substituting the latter into the former yields your recurrence for $a_n$. Since $b_n$ is just $a_n$ shifted, it satisfies the same recurrence. And your $f$ is the sum of the two, so it also satisfies the same recurrence.