Question 189
In a mathematics class, the teacher shows an apparatus containing $n$ switches, where each switch can be in any of three positions, labelled 1–3, and $n \gt 1$. Initially, all switches are in position 1, and we need to move the switches so that all are in position 2. The teacher shows one method of doing this that involves exactly $n + 1$ steps, where each *step* changes the position of exactly one switch.
Let $c_n$ be the number of $(n+1)$-step methods for altering the apparatus in this way, *not including the teacher's method*. Two methods are the same only if they involve the same steps in the same order. Show that $c_n$ has no factor $k$ satisfying $1 \lt k \lt n+2$, and that $n+2$ is a factor of $c_n$ if and only if $n+2$ is prime.
Let $c_n$ be the number of $(n+1)$-step methods for altering the apparatus in this way, *not including the teacher's method*. Two methods are the same only if they involve the same steps in the same order. Show that $c_n$ has no factor $k$ satisfying $1 \lt k \lt n+2$, and that $n+2$ is a factor of $c_n$ if and only if $n+2$ is prime.