
Problem 10.3. Let $n$ be a natural number. Find the number of sequences $a_{1} a_{2} \ldots a_{2 n}$, where $a_{i}=+1$ or $a_{i}=-1$ for $i=1,2 \ldots, 2 n$, such that

$$
\left|\sum_{i=2 k-1}^{2 l} a_{i}\right| \leq 2
$$

for all $k$ and $l$ for which $1 \leq k \leq l \leq n$.


Solution: It is clear that a sequence having $a_{2 k-1}+a_{2 k}=0$ for $1 \leq k \leq n$ satisfies the condition of the problem, because any sum of the form $\sum_{i=2 k-1}^{2 l} a_{i}$ equals zero. There are $2^{n}$ such sequences. Let us determine the number of sequences such that there exists a $k$ for which $a_{2 k-1}+a_{2 k} \neq 0$. Let $k_{1}, k_{2}, \ldots, k_{s}$ be all $k$ with the above property. It is easily seen that if $a_{2 k_{i}-1}+a_{2 k_{i}}=2(-2)$, then $a_{2 k_{i+1}-1}+a_{2 k_{i+1}}=-2$ (2). Therefore all sums $a_{2 k_{i}-1}+a_{2 k_{i}}$ (and so also $a_{2 k_{i}-1} a_{2 k_{i}}$ ) are uniquely determined by $a_{2 k_{1}-1}+a_{2 k_{1}}$ (there are two possibilities for $a_{2 k_{1}-1} a_{2 k_{1}}$ ). There are two possibilities for any of the remaining $n-s$ pairs (for which $a_{2 t-1}+a_{2 t}=0$ ). Therefore there are

$2^{n}+2 \cdot 2^{n-1}\binom{n}{1}+2 \cdot 2^{n-2}\binom{n}{2}+\cdots+2 \cdot 2^{n-k}\binom{n}{k}+\ldots+2 \cdot 2\binom{n}{n-1}+2 \cdot\binom{n}{n}$.
sequences with the required property. By adding and subtracting $2^{n}$ to and from the above expression we get:

2. $\left(2^{n}\binom{n}{0}+2^{n-1}\binom{n}{1}+2^{n-2}\binom{n}{2}+\cdots+2\binom{n}{n-1}+\binom{n}{n}\right)-2^{n}=2 \cdot 3^{n}-2^{n}$

Thus there are $2 \cdot 3^{n}-2^{n}$ sequences.
