Problems

I have \(n\) fence posts placed in a line and, as part of my spouse's birthday celebrations, I wish to paint them using three different colours red, white and blue in such a way that no adjacent fence posts have the same colours. (This allows the possibility of using fewer than three colours as well as exactly three.) Let \(r_{n}\) be the number of ways (possibly zero) that I can paint them if I paint the first and the last post red and let \(s_{n}\) be the number of ways that I can paint them if I paint the first post red but the last post either of the other two colours. Explain why \(r_{n+1}=s_{n}\) and find \(r_{n}+s_{n}.\) Hence find the value of \(r_{n+1}+r_{n}\) for all \(n\geqslant1.\) Prove, by induction, that \[ r_{n}=\frac{2^{n-1}+2(-1)^{n-1}}{3}. \] Find the number of ways of painting \(n\) fence posts (where \(n\geqslant3\)) placed in a circle using three different colours in such a way that no adjacent fence posts have the same colours.