Auswahlwettbewerb zur Internationalen Mathematik-Olympiade

Solution:

We denote $S_{n}=x_{1}+\ldots+x_{n}$ and carry out a proof by induction. Direct computation gives $x_{1}=1$, $x_{2}=-1$, $x_{3}=1$, $x_{4}=1$ and hence $S_{n} \geq 0$ for $1 \leq n \leq 4$.

Now we assume that $S_{k} \geq 0$ holds for all natural numbers $k<n$, and we claim $S_{n} \geq 0$.

For this we distinguish four cases.

Case 1: $n=4m$. We have
$$S_{n}=\sum_{i=1}^{m}\left(x_{4i-3}+x_{4i-2}+x_{4i-1}+x_{4i}\right)=\sum_{i=1}^{m}\left(x_{2i-1}-x_{2i-1}-x_{2i}-x_{2i}\right)$$
$$=-2 \sum_{i=1}^{m} x_{2i}=2 \sum_{i=1}^{m} x_{i}=2 S_{m} \geq 0.$$

Case 2: $n=4m+1$. We have $S_{n}=2 S_{m}+x_{4m+1}=2 S_{m}+x_{2m+1}=2 S_{m}+(-1)^{m} x_{m+1}$.

Case 2.1: $m$ is odd. Then $S_{m}$ is also odd, so $2 S_{m} \geq 2$ and $S_{n} \geq 1>0$.

Case 2.2: $m$ is even. We have $S_{n}=2 S_{m}+x_{m+1}=S_{m}+S_{m+1} \geq 0$.

Case 3: $n=4m+2$. We have $S_{n}=S_{n-2}+x_{4m+1}+x_{4m+2}=S_{n-2}+x_{2m+1}-x_{2m+1}=S_{n-2} \geq 0$.

Case 4: $n=4m+3$. We have $S_{n}=S_{n+1}-x_{n+1}=2 S_{m+1}+x_{2m+2}=2 S_{m+1}-x_{m+1}=S_{m}+S_{m+1} \geq 0$.