MathNet 2010 — Part 03 Question 39

Let $n$ be a positive integer. Determine the number of sequences $x_1, x_2, \dots, x_{2n-1}, x_{2n}$, with $x_i = 1$ or $-1$, and such that $\left|\sum_{i=2k-1}^{2m} x_i\right| \le 2$ for all integers $k, m$, with $1 \le k \le m \le n$.