Problems

The sequence \(u_n\) (\(n= 1, 2, \ldots\)) satisfies the recurrence relation \[ u_{n+2}= \frac{u_{n+1}}{u_n}(ku_n-u_{n+1}) \] where \(k\) is a constant. If \(u_1=a\) and \(u_2=b\,\), where \(a\) and \(b\) are non-zero and \(b \ne ka\,\), prove by induction that \[ u_{2n}=\Big(\frac b a \Big) u_{2n-1} \] \[ u_{2n+1}= c u_{2n} \] for \(n \ge 1\), where \(c\) is a constant to be found in terms of \(k\), \(a\) and \(b\). Hence express \(u_{2n}\) and \(u_{2n-1}\) in terms of \(a\), \(b\), \(c\) and \(n\). Find conditions on \(a\), \(b\) and \(k\) in the three cases:

1. the sequence \(u_n\) is geometric;
2. \(u_n\) has period 2;
3. the sequence \(u_n\) has period 4.

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.