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.
I am asked to find a recurrence relation then solve it. (already done)
Lastly im asked to count $a_{10}$ directly that is count the cases with exactly 0 blue chips, exactly 1 blue chip, etc and sum all the of them up to get a value for $a_{10}$ then check it against my recurrence relation's solution. but i cant figure out how to count this in a nice way...
To arrange $n$ chips with exactly $k>0$ of them blue, and none of the blues consecutive, we can consider two cases: the top chip is blue, or the top chip is not blue.
In total, we have $\binom{n-k}{k} + \binom{n-k}{k-1} = \binom{n-k+1}{k}$ ways to rearrange the chips. (We could also have done this in one go, by placing a fictional non-blue chip on top, and just considered the first case but for $n+1$.)
Then, of course, we must choose the non-blue chips, and we get $\binom{n-k+1}{k} \cdot 3^{n-k}$.
If there were only two colors of chips (e.g. blue and red), then there would be Fibonacci many ways to arrange the chips with no two blues adjacent, and this same argument would give us the well-known identity $$F_{n+2} = \sum_{k=0}^{\left\lfloor\frac{n+1}{2}\right\rfloor} \binom{n-k+1}{k}.$$