51st IMO Shortlisted Problems

We start with some observations. First, from the definition of $x_i$ it follows that for each positive integer $k$ we have $$x_{4k-3}=x_{2k-1}=-x_{4k-2}\text{ and }{x}_{4k-1}=x_{4k}=-x_{2k}=x_k.$$ Hence, denoting $S_n={\sum }_{i=1}^n{x}_i$, we have $$S_{4k}=\sum _{i=1}^k\left(\left(x_{4k-3}+x_{4k-2}\right)+\left(x_{4k-1}+x_{4k}\right)\right)=\sum _{i=1}^k\left(0+2x_k\right)=2S_k$$ $$S_{4k+2}=S_{4k}+\left(x_{4k+1}+x_{4k+2}\right)=S_{4k}$$ Observe also that $S_n={\sum }_{i=1}^n{x}_i\equiv {\sum }_{i=1}^{n}1=n(\mathrm{mod}2)$. Now we prove by induction on $k$ that $S_i\ge 0$ for all $i\le 4k$. The base case is valid since $x_1=x_3=x_4=1$, $x_2=-1$. For the induction step, assume that $S_i\ge 0$ for all $i\le 4k$. Using the relations above, we obtain $$S_{4k+4}=2S_{k+1}\ge 0,S_{4k+2}=S_{4k}\ge 0,S_{4k+3}=S_{4k+2}+x_{4k+3}=\frac{S_{4k+2}+S_{4k+4}}{2}\ge 0$$ So, we are left to prove that $S_{4k+1}\ge 0$. If $k$ is odd, then $S_{4k}=2S_k\ge 0$; since $k$ is odd, $S_k$ is odd as well, so we have $S_{4k}\ge 2$ and hence $S_{4k+1}=S_{4k}+x_{4k+1}\ge 1$. Conversely, if $k$ is even, then we have $x_{4k+1}=x_{2k+1}=x_{k+1}$, hence $S_{4k+1}=S_{4k}+x_{4k+1}=2S_k+x_{k+1}=S_k+S_{k+1}\ge 0$. The step is proved.

---

Alternative solution.

We will use the notation of $S_n$ and the relations above from the previous solution. Assume the contrary and consider the minimal $n$ such that $S_{n+1}<0$; surely $n\ge 1$, and from $S_n\ge 0$ we get $S_n=0$, $x_{n+1}=-1$. Hence, we are especially interested in the set $M=\{n:S_n=0\}$; our aim is to prove that $x_{n+1}=1$ whenever $n\in M$ thus coming to a contradiction. For this purpose, we first describe the set $M$ inductively. We claim that (i) $M$ consists only of even numbers, (ii) $2\in M$, and (iii) for every even $n\ge 4$ we have $n\in M⟺[n/4]\in M$. Actually, (i) holds since $S_n\equiv n(\mathrm{mod}2)$, (ii) is straightforward, while (iii) follows from the relations $S_{4k+2}=S_{4k}=2S_k$. Now, we are left to prove that $x_{n+1}=1$ if $n\in M$. We use the induction on $n$. The base case is $n=2$, that is, the minimal element of $M$; here we have $x_3=1$, as desired. For the induction step, consider some $4\le n\in M$ and let $m=[n/4]\in M$; then $m$ is even, and $x_{m+1}=1$ by the induction hypothesis. We prove that $x_{n+1}=x_{m+1}=1$. If $n=4m$ then we have $x_{n+1}=x_{2m+1}=x_{m+1}$ since $m$ is even; otherwise, $n=4m+2$, and $x_{n+1}=-x_{2m+2}=x_{m+1}$, as desired. The proof is complete.