A team plays a series of games, each of which results in either a win (W), a draw (D), or a loss (L). Let $S_n$ denote the number of possible sequences for a team which never loses two successive games in a series of $n$ games. Prove that $S_{2n}$ and $S_{2n + 1}$ are both divisible by $2^n$.
(Source: Singapore-Cambridge GCE A-Level N2007/9810/01/Q9)
I was able to come up with a recursive formula for $S_n$: Suppose the team lost the $n$th game. Then the team must have either won or gotten a draw in the previous $n-1$th game. There are $2S_{n - 2}$ possible cases.
Suppose instead the team did not lose the $n$th game. Then the team must have either won or gotten a draw for the $n$th game. There are $2S_{n-1}$ possible cases.
Hence, by the Addition Principle, $S_n = 2S_{n-1} + 2S_{n - 2}$.
However, I'm stuck at the second part. It could be possible to use induction (in fact, I'm sure this is the "correct" way), but I was looking at a combinatorial proof instead.
Define an equivalence relation on the set of permitted sequences of $n$ win/lose/draw if the locations of the losses are the same.
If there are $k$ losses, then the equivalence class has $2^{n-k}$ elements, since the other times can be either win or draw, freely chosen. But $k\leq \left\lceil\frac{n}{2}\right\rceil$ so the number of elements in each equivalence class must be divisible by $2^{ \left\lfloor\frac{n}{2}\right\rfloor}$ since $\left\lceil\frac{n}{2}\right\rceil + \left\lfloor\frac{n}{2}\right\rfloor = n$.
So $S_n$ must be divisible by $2^{ \left\lfloor\frac{n}{2}\right\rfloor}$, which is what you are trying to prove.
You can go somewhat further.
When $n$ is odd, there is only one way to get the maximum number of losses, so the largest power of $2$ that divides $S_n$ is $2^{\left\lfloor\frac{n}{2}\right\rfloor}$.
When $n$ is even, there are $n/2+1$ different ways to get the maximum loses, and therefore when $n$ is divisible by $4$, $S_n$ is divisible by exactly $2^{n/2}$, while if $n$ is not divisible by $4$, $S_n$ is divisible by $2^{n/2+1}$, and possibly higher powers of $2$.