1.3. Find the number of 16 -tuples $\left(x_{1}, x_{2}, \ldots, x_{16}\right)$ such that
(i) $x_{i}= \pm 1$ for $i=1, \ldots, 16$,
(ii) $0 \leq x_{1}+x_{2}+\cdots+x_{r}<4$, for $r=1,2, \ldots, 15$,
(iii) $x_{1}+x_{2}+\cdots+x_{10}=4$.
1.3. 1st solution

More generally, let $S_{n}$ be the set of all $n$-tuples $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ such that
(i) $x_{i}= \pm 1$ for $i=1, \ldots, n$,
(ii) $0 \leq x_{1}+x_{2}+\cdots+x_{r}<4$, for $r=1,2, \ldots, n-1$,
(iii) $x_{1}+x_{2}+\cdots+x_{n}=4$.

Also let $S_{n}^{\prime}$ be the set of all $n$-tuples $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ such that
(i) $x_{i}= \pm 1$ for $i=1, \ldots, n$,
(ii) $-2 \leq x_{1}+x_{2}+\cdots+x_{r}<2$, for $r=1,2, \ldots, n-1$,
(iii) $x_{1}+x_{2}+\cdots+x_{n}=2$.

Let $\left|S_{n}\right|=a_{n}$ and $\left|S_{n}^{\prime}\right|=b_{n}$. First note that $a_{n}=0$ if $n$ is odd. Hence we consider only even values of $n$.

Let $\left(x_{1}, x_{2} \ldots, x_{2 k}\right)$ be an element in $S_{2 k}$. Then $\left(x_{1}, x_{2}\right)=(1,1)$ or $(1,-1)$. If $\left(x_{1}, x_{2}\right)=$ $(1,1)$, then $\left(x_{3}, x_{4} \ldots, x_{2 k}\right)$ is an element of $S_{2 k-2}^{\prime}$. If $\left(x_{1}, x_{2}\right)=(1,-1)$, then $\left(x_{3}, x_{4} \ldots, x_{2 k}\right)$ is an element of $S_{2 k-2}$. Conversely, if each element of $S_{2 k-2}^{\prime}$ is augmented at the beginning by two ones, it gives rise to an element of $S_{2 k}$. Similarly, if each element of $S_{2 k-2}$ is augmented at the beginning by 1 and -1 , it gives rise to an element of $S_{2 k}$. This shows that $a_{2 k}=b_{2 k-2}+a_{2 k-2}$.
Next consider an element $\left(x_{1}, x_{2} \ldots, x_{2 k}\right)$ in $S_{2 k}^{\prime}$. Then $\left(x_{1}, x_{2}\right)=(1,-1),(-1,1)$ or $(-1,-1)$. Hence, $\left(x_{3}, x_{4} \ldots, x_{2 k}\right)$ is an element of $S_{2 k-2}^{\prime}$ if $\left(x_{1}, x_{2}\right)=(1,-1)$ or $(-1,1)$, and it is an element of $S_{2 k-2}$ if $\left(x_{1}, x_{2}\right)=(-1,-1)$. By augmenting each element of $S_{2 k-2}^{\prime}$ at the beginning by either $1,-1$ or $-1,1$, it gives rise to an element of $S_{2 k}^{\prime}$. Similarly, by augmenting each element of $S_{2 k-2}$ at the beginning by $-1,-1$, we get an element of $S_{2 k}^{\prime}$. This shows that $b_{2 k}=a_{2 k-2}+2 b_{2 k-2}$.
By eliminating the $b_{2 k}$ 's in the above two difference equations, we have $a_{2 k}-3 a_{2 k-2}+a_{2 k-4}=$ 0 . The initial conditions are $a_{2}=0$ and $a_{4}=1$. By solving this difference equation, it gives
$$
a_{2 k}=\frac{1}{\sqrt{5}}\left(\frac{3+\sqrt{5}}{2}\right)^{2 k-2}-\frac{1}{\sqrt{5}}\left(\frac{3-\sqrt{5}}{2}\right)^{2 k-2} .
$$
2nd solution
Let $S_{n}^{\prime \prime}$ be the set of all $n$-tuples $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ such that
(i) $x_{i}= \pm 1$ for $i=1, \ldots, n$,
(ii) $0 \leq x_{1}+x_{2}+\cdots+x_{r}<4$, for $r=1,2, \ldots, n-1$,
(iii) $x_{1}+x_{2}+\cdots+x_{n}=2$.

Let $\left|S_{n}^{\prime \prime}\right|=c_{n}$. Again, we only have to consider even values of $n$. Note that each sequence in $S_{2 k}$ must end in two " 1 "s. By dropping these two ones, we obtain a sequence in $S_{2 k-2}^{\prime \prime}$. Conversely, each sequence in $S_{2 k-2}^{\prime \prime}$ can be augmented at the end by two "1"s to get a sequence in $S_{2 k}$. Hence $a_{2 k}=c_{2 k-2}$.
Let's examine the end terms of each sequence in $S_{2 k}^{\prime \prime}$. The last three terms of any sequence in $S_{2 k}^{\prime \prime}$ are as follow:
$$
-111,1-11,11-1,-1-11,-11-1 .
$$

For the first three cases, one can replace them by a single " 1 " to get a member of $S_{2 k-2}^{\prime \prime}$. For the last two cases, one can drop the last two terms to get a member of $S_{2 k-2}^{\prime \prime}$.
Conversely, for any sequence in $S_{2 k-2}^{\prime \prime}$, which ends in a " 1 ", one can replace the " 1 " by any one of the first three endings in $\left(^{*}\right)$ to get a sequence in $S_{2 k}^{\prime \prime}$.
Let the number of sequences in $S_{2 k-2}^{\prime \prime}$ which end in a " 1 " be $x$. Let the number of sequences in $S_{2 k-2}^{\prime \prime}$ which end in a " -1 " be $y$. In the latter case, observe that if this last "-1" is replaced by a "1", then a sequence in $S_{2 k-2}$ is obtained. Hence, $y=a_{2 k-2}$.
Similarly, for any sequence in $S_{2 k-2}^{\prime \prime}$ which ends in a "-1", it can be replaced by any one of the last two endings in $\left(^{*}\right)$ to get a sequence in $S_{2 k}^{\prime \prime}$.
Therefore, $c_{2 k}=3 x+2 y=3(x+y)-y=3 c_{2 k-2}-y$. That is $a_{2 k+2}=3 a_{2 k}-a_{2 k-2}$. This is the same difference equation in solution 1 .