STEP II Q2
(Proving that r(n+1) = s(n).)
Well, r(n+1) is the number of ways to paint n+1 posts such that the first and last post are red. If we ignore the last post, this is the same as painting the first post red and the post before last any of the two other colors (because no two adjacent posts can have the same color) - but there are s(n) ways to do this. So r(n+1) = s(n).
(Finding r(n) + s(n).)
There are r(n) + s(n) ways to paint the fence if we start with a red post. Now say we painted the first post red; we're then left with n-1 posts to deal with, subject to the restriction that the first post must either be white or blue. Say the first post is white, then there are r(n-1) + s(n-1) ways to paint the remaining posts. Similarly, if instead the first post is blue, then there are also r(n-1) + s(n-1) ways to paint the remaining posts.
Thus, for n>=1,
r(n) + s(n) = 2(r(n-1) + s(n-1))
= 2^(n-1) (r(1) + s(1))
= 2^(n-1) (1 + 0)
= 2^(n-1)
(r(n+1) + r(n) for n>=1.)
So, for n>=1,
r(n+1) + r(n) = s(n) + r(n) = 2^(n-1)
(Proving the formula given for r(n).)
First we check if it holds for n=1:
r(1) = (2^0 + 2(-1)^0)/3 = 3/3 = 1, as expected.
Now let's assume that it holds for n=k. Then, by what we found r(n+1) + r(n) to be,
r(k+1) = 2^(k-1) - r(k)
= 2^(k-1) - [2^(k-1) + 2(-1)^(k-1)]/3
= [3*2^(k-1) - 2^(k-1) - 2(-1)^(k-1)]/3
= (2^k + 2(-1)^k)/3
Thus, by induction, the formula is correct for positive integral n.
(Posts in a circle bit.)
Suppose you have n+1 posts in a line. There are r(n+1) ways to paint the first post and the last post using the same color. Then if you wrap this line around to form a circle, and disregard the last post, you will get a circle fence painted in the required way. Of course, all such arrangement arise like this. That is, if you have such a circle fence, pick any post and unravel the circle at that bit and form a line; at the end of the line place a post of the same color as the same one. Now to account for the 3 colors, multiply by 3.*
So the answer is: 3r(n+1) ways.
----------------------------------------
* Thanks to DFranklin for noticing this.