1. The sequence $\left(x_{n}\right)_{n=1}^{\infty}$ of integers with the first term $x_{1}=1$ satisfies the condition

$$
x_{n}= \pm x_{n-1} \pm \ldots \pm x_{1}
$$

with an appropriate choice of signs “+” and “-” for any $n>1$, for example $x_{2}=-x_{1}$, $x_{3}=-x_{2}+x_{1}, x_{4}=x_{3}-x_{2}-x_{1}, \ldots$ For a given $n$, determine all possible values of $x_{n}$.
SOLUTION. Let's list the values that the first terms of the given sequence can take. We get

$$
\begin{gathered}
x_{1}=1, \quad x_{2} \in\{-1,1\}, \quad x_{3} \in\{-2,0,2\}, \quad x_{4} \in\{-4,-2,0,2,4\}, \\
x_{5} \in\{-8,-6,-4,-2,0,2,4,6,8\} .
\end{gathered}
$$

Notice that all the terms we have listed are integers. It is also clear that for $i>2$, each term $x_{i}$ is an even number. (Another observation is that if we find a sequence for which $x_{i}=a$ for some number $a$ and a given $i>1$, then there also exists a sequence for which $x_{i}=-a$.)

Let's determine the largest and the smallest value that the number $x_{n}$ can take (depending on $n$). Let $a_{i}$ denote the largest value that the term $x_{i}$ can take. Since there are only a finite number of sequences of length $i$ satisfying the given properties, the maximum $a_{i}$ exists and is clearly positive. For each $i>1$, there must be a sequence $x_{1}, \ldots, x_{i-1}$ such that

$$
a_{i}= \pm x_{i-1} \pm \ldots \pm x_{1} \leqq\left|x_{i-1}\right|+\ldots+\left|x_{1}\right| \leqq a_{i-1}+\ldots+a_{1}
$$

We know that $a_{1}=1, a_{2}=1, a_{3}=2$. Using the previous formula, let's prove that $a_{i}=2^{i-2}$ for every $i>1$.

We will prove this by mathematical induction with respect to $i$.

