Let $s_n = x_1 + x_2 + \ldots + x_n$. We first note that $s_k = x_1 + x_2 + \cdots + x_k \equiv 1 + 1 + \cdots + 1 \equiv k \pmod{2}$. Next, we note that \begin{align*} x_{4k+1} &= x_{2(2k+1) - 1} = (-1)^{2k+2} x_{2k+1} = x_{2(k+1)-1} = (-1)^k x_{k+1} \\ x_{4k+2} &= -x_{2k+1} = (-1)^{k+1} x_{k+1} \\ x_{4k+3} &= x_{2(2k+2)-1} = (-1)^{2k+3} x_{2k+2} = x_{k+1} \\ x_{4k+4} &= -x_{2k+2} = x_{k+1}. \end{align*} In particular, we have $x_{4k+1} + x_{4k+2} = 0$ and $x_{4k+1} + x_{4k+2} + x_{4k+3} + x_{4k+4} = 2x_{k+1}$, whence $s_{4k+2} = s_{4k}$ and $s_{4k} = 2s_k$ for all $k \geq 1$. Suppose for the sake of contradiction that $s_k < 0$ for some $k$; take the minimal such $k$. It is clear that $k > 4$. Since $s_{k-1} \geq 0$ by minimality of $k$, and $s_{k-1} = s_k - x_k \leq s_k + 1 \leq 0$, we have $s_{k-1} = 0$ and $x_k = -1$. If $k \equiv 1 \pmod{4}$, let $k = 4j + 1$. Then $s_{k-1} = s_{4j} = 2s_j = 0$, so $s_j = 0$, whence $j$ must be even. Furthermore, since $s_{j+1} > 0$ (by minimality of $k$), $x_{j+1} = 1$, so $x_k = s_{4j+1} = (-1)^j x_{j+1} = 1 \neq -1$, contradiction. If $k \equiv 3 \pmod{4}$, let $k = 4j + 3$. Then $s_{4j + 2} = s_{4j} = 2s_j = 0$, so $s_j = 0$,. Furthermore, since $s_{j+1} > 0$ (by minimality of $k$), $x_{j+1} = 1$, so $x_k = x_{4j+3} = x_{j+1} = 1 \neq -1$, contradiction. It follows that $s_k \geq 0$ for all positive integers $k$, as desired.

Let $S_n = x_1+x_2+...+x_n$. We also define $S_0 = 0$ Fact 1: $|x_k| = 1$ for every $k\ge 1$ Proof: We do induction on $k$. It is true for $x_1$. Let $n>1$ and suppose it is true for every $0<k < n$. If $n=2m$, we have $0<m<n$, then $|x_m|=1$, and so $|x_n|=|x_m|=1$ If $n=2m-1$, we have that $0<m<n$, then $|x_m|=1$, and so $|x_n|=|x_m|=1$. Fact 2: $S_{4m}=2S_{m}$ for every $m\ge 0$ Proof: Notice first that for every $m\ge 1$ we have: $x_{4m}=-x_{2m}=x_{m} $ $x_{4m-1}=-x_{2m}=x_{m}$ $x_{4m-2}=-x_{2m-1}=(-1)^mx_m$ $x_{4m-3}=x_{2m-1}=(-1)^{m+1}x_m$ We do induction on $m$. It is true for $m=0$. Let $m>0$ and suppose it is true for $m-1$. $S_{4m} = S_{4m-4} + x_{4m-3}+x_{4m-2}+x_{4m-1}+x_{4m} = S_{4m-4} + 2x_m = 2S_{m-1} + 2x_m = S_m$ Now we prove the problem by induction on $n$. It is easy to see that $S_n\ge$ 0 for $n=0, 1, 2, 3, 4$. Let $n>4$ and suppose that $S_k\ge 0$ for every $0\le k<n$. Let $m = \lceil{n/4}\rceil$. Then $1<m<n$ Then $S_{m-1}\ge 0$ and $S_m\ge 0$ by induction hypotesis. If $S_{m-1} = 0$ then 0 is the sum of $m-1$ numbers that are $\pm 1$ and so $m$ is odd. Also $x_m = 1$ since $S_m \ge 0$. Then $x_{4m-3} = 1, x_{4m-2} = -1, x_{4m-1}=1, x_{4m}=1$. We also have $S_{4m-4}=S{m-1} =0$. Then $S_{4m-3}, S_{4m-2}, S_{4m-1}, S_{4m}$ are all $\ge 0$. Then $S_n\ge 0$, since $n\in\{4m-3,4m-2,4m-1,4m\}$ If $S_{m-1}> 0$, then $S_{m-1}\ge 1$, and so $S_{4m-4}\ge 2$. $S_{4m-3} = S_{4m-4}+x_{4m-3}\ge 2-1= 1$ $S_{4m-2} = S_{4m-4}+x_{4m-3}+x_{4m-3} = S{4m-4}\ge 2$ $S_{4m-1} = S_{4m-2}+x_{4m-1}\ge 2-1 = 1$ $S_{4m}= S_{4m-2}+x_{4m-1}+x_{4m}\ge 2-1-1=0$ Then $S_{4m-3}, S_{4m-2}, S_{4m-1}, S_{4m}$ are all $\ge 0$. Then $S_n\ge 0$, since $n\in\{4m-3,4m-2,4m-1,4m\}$ In both cases we have that $S_n\ge 0$. Then, by induction $S_n\ge 0$ for every $n\ge 0$

We can notice that the sequence is periodic with period 16. So, we examine the cases: For, 16k, k positive integer. For, 16k+1 ... For, 16k+2 ... ... For, 16k+15 ... From the above cases is easy to see that the statement is true.

see also here.

TheIronChancellor wrote: We can notice that the sequence is periodic with period 16. By my lights, it's not. We compute $x_9 = +1$ but $x_{25} = -1$. The official solution actually provides a result from which we infer the sequence is not periodical (they prove that the set of indices $n$ for which $\sum_{k=1}^n x_k = 0$ is made by precisely those positive integers not containing digits $1$ nor $3$ when written in numeration basis $4$).

Without even doing any computation, one can see that claim is absurd by the fact that $x_{4k} = x_k$. So if $x_{16k} = x_{16k+16}$ for all $k$ (a weaker claim), then $x_{4k+4} = x_{4k}$ and $x_{k+1} = x_k$, implying the whole sequence is constant.

I found the following interesting recurrence: For $n \geq 1, x_{2^n+k} = x_k$ for $ 1 \leq k \leq 2^{n-1}$ $x_{2^n+k} = -x_k$ for $ 2^{n-1}+1 \leq k \leq 2^n$ This is easily proven using induction. This approach leads to a solution, which is not nearly as nice as the solutions already posted.

$u_n = x_1 + x_2 + \cdots + x_n$ $x_ {4k} =- x_ {2k} = x_k$ $x_ {2k +1} = (-1) ^ k x_{k +1}$ $x_ {4k +1} = (-1) ^{2k} x_{2k +1} = x_{2k +1}$ $x_ {4k +2} = x_{2k +1}$ $x_ {4k +3} = x_{2 (2k +1) +1} = (-1) ^{2k +1} x_{2k+2} = - x_ {2k +2} = x_{k +1}$ $x_ {4k +4} = x_{4(k +1)} = x_ {k +1}$ $u_ {4k} = 2u_k$ $u_ {4k +1} = u_{4k} + x_{4k+1} = 2u_k + x_{4k +1}$ $u_ {4k +2} = u_{4k} = u_2u_k$ $u_ {4k +3} = u_{4k} + x_{4k +3} = 2u_k + x_{4k+3}$ By strong induction on n, we'll prove that whenever $u_{n-1}=0$, then $x_n = 1$, which instantly solves the problem. Hypothesis of strong induction is : for all k<n, $u_{k-1} = 0 \implies x_k = 1$ Suppose $u_{n-1} = 0$ : $u_{n-1} = 0 \implies$ n is odd (even sum of (n-1) odd elements, so n-1 is even) - If n = 4k +1: $u_{4k +1} = 2u_k + x_{4k +1}$ But $u_{n-1} = 0 \implies u_{4k} = 0 \implies 2u_k = 0 \implies u_k = 0$, which implies at the same time that k is even (even sum of k odd elements) and (using also the hypothesis of induction for k) that $x_{k +1} = 1$. Consequently : $u_{4k +1} = 2u_k + x_{4k +1} = x_{4k +1} = x_{2k +1} = (-1) ^ k x_{k +1} = 1$. - If n = 4k +3: $u_{4k +3} = 2u_k + x_{4k +3}$ But $u_{n-1} = 0 \implies u_{4k+ 2} = 0 \implies u_{4k} = 0 \implies 2u_k = 0 \implies u_k=0$, which implies (using the hypothesis of induction for k) that $x_{k +1} = 1$ Hence : $u_{4k +3} = 2u_k + x_{4k +3} = x_{4k +3} = x_{k +1} = 1$. End of induction.

Let $S_i = x_1 + x_2 + \dots + x_i$. We will show that $S_i \ge 0$ for all $i \in \mathbb{N}$ by inducting on groups of four terms. First note that $x_1 = 1$, $x_2 = -1$, $x_3 = 1$ and $x_4 =1$, which implies that $S_i \ge 0$ for $i=1,2,3,4$. Now suppose that $S_i \ge 0$ for all $i=1,2,\dots, 4n$. First note that for all $k \in \mathbb{N}$, it follows that $x_{4k+1}=x_{2k+1}$, $x_{4k+2}=-x_{2k+1}$, $x_{4k+3}=-x_{2k+2}=x_{k+1}$ and $x_{4k+4}=-x_{2k+2}=x_{k+1}$. Adding yields that $x_{4k+1}+x_{4k+2}=0$ and that $x_{4k+1}+x_{4k+2}+x_{4k+3}+x_{4k+4}=2x_{k+1}$ which imply that $S_{4k+2}=S_{4k}=2S_k$ for all $k \in \mathbb{N}$. Hence $S_{4n+2}=S_{4n} \ge 0$ and $S_{4n+4}=S_{n+1} \ge 0$. Now it suffices to show that $S_{4n+1}$ and $S_{4n+3}$ are nonnegative. Assume for contradiction that $S_{4n+3} <0$. Since $S_{4n+3}=S_{4n+2}+x_{4n+3}$ and $S_{4n+2} \ge 0$, for this to occur it must follow that $x_{4n+3}=-1$ and $S_{4n+2}=0$. However, since $x_{4n+4}=x_{4n+3}$, this would imply that $S_{4n+4} = -2$ which is a contradiction. Now assume for contradiction that $S_{4n+1}<0$. Since $S_{4n} \ge 0$, this would require that $x_{4n+1}=-1$ and that $S_{4n}=0$. However, this implies that $x_{2n+1}=-1$ and $S_n=0$. If $n$ is odd, then $S_n$ is also an odd number which implies that $S_n \neq 0$. Hence $n$ is even. This implies that $x_{2n+1}=x_{n+1}=-1$ and hence that $S_{n+1}=S_n + x_{n+1}=-1$ which is a contradiction. This completes the induction.

If n is an odd number,we have x_n=1 and if n is an even number,we have x_n=-1[*]

Wrong, $x_4=1$ for example

Sorry to revive this old thread. Is it possible to find an explicit formula for $x_n$ ( such as when write $n$ in an appropriate base etc.)?

To find the value of $x_n$, split the digits of $n-1$ into $m$ blocks of single $1$'s and blocks of contiguous $0$'s. For example, the number \[ 1\ 1\ 1\ 0000\ 1\ 000\ 1\ 0 \] contains $8$ blocks. Now $x_n=(-1)^m$. (The exception is $x_1=1$. How can we deal with this? Here we view $0$ as an empty string after throwing out the leading zero, and there are zero blocks. Thus $x_1=(-1)^0$, as desired.)

orl wrote: A sequence $x_1, x_2, \ldots$ is defined by $x_1 = 1$ and $x_{2k}=-x_k, x_{2k-1} = (-1)^{k+1}x_k$ for all $k \geq 1.$ Prove that $\forall n \geq 1$ $x_1 + x_2 + \ldots + x_n \geq 0.$ Proposed by Gerhard Wöginger, Austria Outline: We use the principal of contradiction to show the desired result. In particular, we consider $n$ modulo $4.$ Proof. Suppose, for the sake of contradiction, that there exists some $n \in \mathbb{N}$ such that $x_1 + x_2 + ... + x_n < 0.$ Let $N$ be the minimal such $n.$ Throughout the remainder of the proof, we denote by $T_i$ the sum $x_1 + x_2 + ... + x_i.$ Now, by testing all possible residue classes modulo $4$, we show, by the principle of contradiction, that no such $N$ exists. Let $N = 4k + t$ for $k \in \mathbb{N}^{0}$ and $t \in \{1, 2, 3, 4\}.$ First, remark that \[T_{4k} = \sum\limits_{i = 1}^k x_{4i - 3} + x_{4i - 2} + x_{4i - 1} + x_{4i} = \sum\limits_{i = 1}^k x_{2i - 1} - x_{2i - 1} - x_{2i} - x_{2i}\]\[= \sum\limits_{i = 1}^k -2x_{2i} = 2\sum\limits_{i = 1}^k x_i = 2T_k.\] Now, we consider the four possible values for $t$: If $t = 2$ or $4$ it follows that $T_{4k + 2} = -1$ or $T_{4k + 4} = -1$, respectively. Combining the fact that $|x_i| = 1$ for all $i \in \mathbb{N}$ with the minimality of $N$, it follows that $T_{4k + 1} = 0$ or $T_{4k + 3} = 0$, respectively. However, since $|x_i| = 1$ for all $i \in \mathbb{N}$, we see that $T_{4k + 1}$ and $T_{4k + 3}$ must be odd numbers, and therefore are nonzero. This is a contradiction. $\blacksquare$ If $t = 3$, we have that \[0 > T_N = T_{4k + 3} = T_{4k} + \left(x_{4k + 1} + x_{4k + 2} + x_{4k + 3}\right)\]\[= T_{4k} + \left(x_{2k + 1} - x_{2k + 1} - x_{2k + 2}\right) = T_{4k} + -x_{2k + 2} = 2T_k + x_{k + 1} = T_k + T_{k + 1}.\] Therefore, at least one of $T_k, T_{k + 1}$ is less than $0$, which contradicts the minimality of $N.$ $\blacksquare$ If $t = 1$, consider $T_{4k + 3}.$ Since $T_{4k + 3}$ is odd and $T_{4k + 1} = -1$, it follows that $T_{4k + 3} = 1, -1, -3.$ However, if $T_{4k + 3} = -1, -3$, by the case of $t = 3$ above, it follows that at least one of $T_k, T_{k + 1}$ is less than $0$, which contradicts the minimality of $N.$ Therefore, we conclude that $T_{4k + 3} = 1.$ Then \[2 = T_{4k + 3} - T_{4k + 1} = x_{4k + 3} + x_{4k + 2} = -x_{2k + 2} - x_{2k + 1} = x_{k + 1} \pm x_{k + 1}\] with the $+, -$ for odd, even $k$, respectively. Clearly we want the $+$, as the $-$ would imply that $2 = 0.$ Therefore, we conclude that $k$ is odd. This implies that $T_k$ is odd. By this fact, and the minimality of $N$, it follows that \[T_{4k + 1} = T_{4k} + x_{4k + 1} = 2T_{k} + x_{4k + 1} \ge 2 + x_{4k + 1} \ge 0\] which contradicts the definition of $N.$ $\blacksquare$ Therefore, $N$ cannot belong to any residue class modulo $4$, which implies that no such $N$ exists. Contradiction. The proof is complete.

We use strong induction. Any base cases are trivial. Now note that $x_{4k}=x_k, x_{4k+1}=x_{2k+1},x_{4k+2}=-x_{2k+1},x_{4k+3}=x_{k+1}$. Hence we have $x_{4k}+x_{4k+1}+x_{4k+2}+x_{4k+3}=x_k+x_{k+1}$. Let $j=\lfloor \tfrac{n}{4}\rfloor$, then $x_1+x_2+x_3+\dots +x_n=(x_1+x_2+\dots +x_{j-1})+(x_1+x_2+\dots +x_{j})+Q$, where $Q$ is the last $0,1,2,3$ terms if $n$ is $3,0,1,2 \pmod{4}$ respectively. We have $(x_1+x_2+\dots +x_{j-1})+(x_1+x_2+\dots +x_{j})\ge 1$, since each sum is at least $0$ and they have different parity. Hence if $n\equiv 3,0 \pmod{4}$ we are obviously done by having $\le 1$ final terms. Also, if $n\equiv 2 \pmod{4}$, then $x_n+x_{n-1}+x_{n-2}=x_{n-2}$, so the last three terms cancel to one and we are done. So the only remaining case is $n\equiv 1 \pmod{4}$. We need to show that $2(x_1+x_2+\dots +x_j)+x_{2j+1}\ge 0$. If $j$ is even, then $x_{2j+1}=x_{j+1}$, so the sum is $(x_1+x_2+\dots +x_j)+(x_1+x_2+\dots +x_{j+1})\ge 0$. But if $j$ is odd, then $2(x_1+x_2+\dots +x_j)\ge 2$ and the result follows, so we are done.

Use \[x_{2^a +1} + x_{2^a +2} + \dots + x_{2^a +k} \ge 0\]and \[x_{2^a +1} + x_{2^a + 2} + \dots + x_{2^{a+2}}= 0\]where $a$ is odd and $1 \le k \le 3 \times 2^a$. Easily proven by induction.

Here is my proof using the powers of $2$ idea (instead of residues mod $4$). Quite lengthy, but natural to come out with. We check by hand that the first $8$ terms of the sequence are $1, -1, 1, 1, 1, -1, -1, -1$, and the sum of first $n$ terms for $1\le n\le 8$ are $1, 0, 1, 2, 3, 2, 1, 0$. For brevity, denote $S_n=x_1+x_2+\cdots +x_n$. First, we will prove that $x_{2^n+i}=x_i$ for $1\le i\le 2^{n-1}$ and $x_{2^n+i}=-x_i$ for $2^{n-1}+1\le i\le 2^n$. Base case is in second paragraph. For inductive step suppose this is true for $n=k-1$, then just note that: i) $x_{2^k+2i-1}=(-1)^{2^{k-1}+i+1}x_{2^{k-1}+i}=(-1)^{i+1}x_i=x_{2i-1}$ for $1\le 2i-1\le 2^{k-1}$. (So that $1\le i\le 2^{k-2}$.) ii) $x_{2^k+2i}=-x_{2^{k-1}+i}=-x_i=x_{2i}$ for $1\le 2i\le 2^{k-1}$. (So that $1\le i\le 2^{k-2}$.) iii) $x_{2^k+2i-1}=(-1)^{2^{k-1}+i+1}x_{2^{k-1}+i}=(-1)^{i+1}(-x_i)=-x_{2i-1}$ for $2^{k-1}+1\le 2i-1\le 2^k$. (So that $2^{k-2}+1\le i\le 2^{k-1}$.) iv) $x_{2^k+2i}=-x_{2^{k-1}+i}=-(-x_i)=-x_{2i}$ for $2^{k-1}+1\le 2i\le 2^k$. (So that $2^{k-2}+1\le i\le 2^{k-1}$.) This proves our claim, in particular, that $S_{4^n}=2^n$, $S_{2\cdot 4^n}=0$, $\forall n \in \mathbb{N}$. Now, we prove even more than the problem statement, that for any $n\in \mathbb{N}$, we have i) $0\le S_i\le 2^n$, $\forall 1\le i\le 4^n$. ii) $0\le S_i\le 2^{n+1}$, $\forall 4^n+1\le 2\cdot 4^n$. We induct on $n$. The base case $n=1$ is again shown in the second paragraph, and they do satisfy (i) and (ii). Suppose that both (i) and (ii) are true for $n=k$, we shall prove this for $n=k+1$ using the hypothesis. So suppose we have $0\le S_i\le 2^k$ $\forall 1\le i\le 4^k$, and $0\le S_i\le 2^{k+1}$, $\forall 4^k+1\le i\le 2\cdot 4^k$. We break our proof into four parts. a) For $2\cdot 4^k+1\le i\le 3\cdot 4^k$, since $S_{2\cdot 4^k}=0$ and $x_{2\cdot 4^k+j}=x_j$ for $1\le j\le 4^k$, then by hypothesis (i), $0\le S_{2\cdot 4^k+j}=S_j\le 2^k$, thus $0\le S_i\le 2^k$ $\forall 2\cdot 4^k+1\le i\le 3\cdot 4^k$. b) For $3\cdot 4^k+1\le i\le 4^{k+1}$, observe that $S_{3\cdot 4^k}=S_{4^k}=2^k$, and $x_{3\cdot 4^k+j}=-x_{4^k+j}$ for $1\le j\le 4^k$. So we have $$S_{3\cdot 4^k+j}=S_{3\cdot 4^k}+\sum^{3\cdot 4^k+j}_{m=3\cdot 4^k+1}{x_m}=2^k-\sum^{4^k+j}_{m=4^k+1}{x_m}=2^k-(S_{4^k+j}-S_{4^k})=2^{k+1}-S_{4^k+j}$$So since by hypothesis (ii) we have $0\le S_{4^k+j}\le 2^{k+1}$, then $0\le 2^{k+1}-S_{4^k+j}=S_{3\cdot 4^k+j}\le 2^{k+1}$ as well. So $0\le S_i\le 2^{k+1}$ $\forall 3\cdot 4^k+1\le i\le 4^{k+1}$. Combining part (a) and part (b) and the hypothesis means $0\le S_i\le 2^{k+1}$ $\forall 1\le i\le 4^{k+1}$. We proceed to prove $0\le S_i\le 2^{k+2}$ $\forall 4^{k+1}+1\le i\le 2\cdot 4^{k+1}$. c) For $4^{k+1}+1\le i\le 6\cdot 4^k$, since $S_{4^{k+1}}=2^{k+1}$, and $x_{4^{k+1}+j}=x_j$ for $1\le j \le 2\cdot 4^k$, then $S_{4^{k+1}+j}=2^{k+1}+S_j$. From hypothesis (i) and (ii), we may combine them to get $0\le S_j\le 2^{k+1}$ $\forall 1\le j\le 2\cdot 4^k$, so we have $2^{k+1}\le S_{4^{k+1}+j}=2^{k+1}+S_j\le 2^{k+2}$ as well. So $0\le 2^{k+1}\le S_i\le 2^{k+2}$ $\forall 4^{k+1}+1\le i\le 6\cdot 4^k$. d) For $6\cdot 4^k+1 \le i\le 2\cdot 4^{k+1}$, observe that $S_{6\cdot 4^k}=2^{m+1}$, and $x_{6\cdot 4^k+j}=-x_{2\cdot 4^k+j}$, thus we have $$S_{6\cdot 4^k+j}=S_{6\cdot 4^k}+\sum^{6\cdot 4^k+j}_{m=6\cdot 4^k+1}{x_m}=2^k+1-\sum^{2\cdot 4^k+j}_{m=2\cdot 4^k+1}{x_m}=2^k-(S_{2\cdot 4^k+j}-S_{4^k})=2^{k+1}-S_{2\cdot 4^k+j}$$So since by the combined hypothesis from part (a) and part (b) we have $0\le S_i\le 2^{k+1}$ $\forall 2\cdot 4^k+1\le i\le 4^{k+1}$, then we also have $0\le 2^{k+1}-S_{2\cdot 4^k+j}=S_{6\cdot 2^k+j}\le 2^{k+1}$ $\forall 1\le j\le 2\cdot 4^k$. This means that $0\le S_i\le 2^{m+1}$ $\forall 6\cdot 4^k+1\le i\le 2\cdot 4^{k+1}$. Combining part (c) and part (d) means $0\le S_i\le 2^{k+2}$ $\forall 4^{k+1}+1\le i\le 2\cdot 4^{k+1}$. This completes the inductive step, thus proving the double induction. So $S_i\ge 0$ for all $i\in \mathbb{N}$ as desired.

We will prove the claim with strong induction. It is clear that it is true when $n=1$, so suppose that it is now true for all positive integers under $n$. Then, we wish to show $x_1+\ldots +x_n\ge 0$. We know that $x_2+x_4+\ldots+x_{2\lfloor n/2\rfloor}=-(x_1+x_2+\ldots+x_{\lfloor n/2\rfloor})$, so we need that $x_1+x_3+\ldots +x_{2\lfloor(n-1)/2\rfloor+1}\ge x_1+\ldots+x_{\lfloor n/2\rfloor}$. For each odd number, we have that $x_{2i-1}=x_i$ if $i$ is odd, and $-x_i$ otherwise. So, the LHS becomes $x_1-x_2+x_3-\ldots$. If $n$ is even, we can cancel out the odds to get $x_2+x_4+\ldots x_{2\lfloor n/4\rfloor}\le 0$, which is clear, since we know this is $-(x_1+x_2+\ldots)$. If $n$ is odd, we actually get $x_{n}\ge 2(x_2+x_4+\ldots+x_{2\lfloor(n-1)/4\rfloor})$. If $\frac{n-1}{2}$ is $2,3\pmod 4$, then the number within the parentheses must be odd. However, it is less than 0. So, the RHS is less than $-2$, which is good enough. Also, if $x_n=1$, then the claim is clear, so we suppose that it is $-1$. If $n=8k+1$, then we know that $x_{8k+1}=x_{4k+1}=x_{2k+1}=-1$, and the RHS is $-2(x_1+x_2+\ldots +x_{2k})$. As $x_1+\ldots+x_{2k+1}\ge 0$, we must have $x_1+\ldots+x_{2k}\ge 1$, which gives the desired result. If $n=8k+3$, then we know $x_{8k+3}=-x_{4k+2}=x_{2k+1}=-1$, and we get a similar result.

Let $s_n=x_1+\cdots+x_n$. We induct on $n$ to show $s_n\ge 0$, base cases trivial. Note that \begin{align*} x_{4k+1} &= x_{2k+1} = (-1)^k x_{k+1}\\ x_{4k+2} &= -x_{2k+1} = (-1)^{k+1} x_{k+1} \\ x_{4k+3} &= -x_{2k+2} = x_{k+1} \\ x_{4k+4}&=-x_{2k+2}=x_{k+1}. \end{align*}In particular, $x_{4k+1} + x_{4k+2} = 0$, and $x_{4k+1} + \cdots + x_{4k+4} = 2x_{k+1}$. Therefore, \begin{align*} s_{4k} &= \sum_{i=0}^{k-1} (x_{4i+1}+x_{4i+2}+x_{4i+3}+x_{4i+4}) = 2\sum_{i=0}^{k-1} x_{i+1} = 2s_k. \end{align*}Also note that $s_{4k+2} = s_{4k}=2s_k$. (At this point, we are basically done by induction; we just need to deal with edge cases.) So by induction, $s_{4k} \ge 0$ and $s_{4k+2} \ge 0$. Now we need to show that $s_{4k+1} \ge 0$ and $s_{4k+3}\ge 0$. We have $s_{4k+1} = 2s_k + x_{4k+1}$. Note that $s_k \equiv 1+\cdots+1\equiv k\mod 2$. If $k$ is odd, then $s_k\equiv 1\mod 2$, so $s_k\ge 1$. Hence $s_{4k+1} = 2s_k + x_{4k+1} \ge 2(1) + (-1) = 1>0$. If $k$ is even, then \[ s_{4k+1} = 2s_k+x_{4k+1} = 2(s_{k+1}-x_{k+1}) + (-1)^k x_{k+1} = 2s_{k+1} - x_{k+1} \ge 2(1) - 1 >0.\]Therefore, $s_{4k+1} \ge 0$. The case $s_{4k+3}$ is very similar, since $s_{4k+3} = s_{4k+4} - x_{4k+4} = 2s_{k+1} - x_{4k+4}$. This completes the induction.

Given $x_{2k+1},x_{2k+2}$ we have $x_{4k+1}=x_{2k+1},x_{4k+2}=-x_{2k+1},x_{4k+3}=-x_{2k+2},x_{4k+4}=-x_{2k+2}$. Clearly $-x_{2k+2}=x_{k+1}$. We now force induction through and work out the base cases later. Observe that \[\sum_{i=1}^{4k} x_i = 2\sum_i^k x_i,\]so induction immediately applies for $4\mid n$. Moreover, induction also applies for $n\equiv 2\pmod{4}$. Otherwise, we need to show that one of \[2\sum_i^k x_i\ge -x_{k+1}\]and \[2\sum_i^k x_i \ge -x_{2k+1}.\]Since each $x_j$ has absolute value $1$, we need to show that $\sum_i^k x_i=0$ implies $x_{2k+1}=x_{k+1}=1$. Observe that regardless the argument implies that if $\sum_i^k x_i$ is even, then $k$ is even. Hence we just need to demonstrate $x_{k+1}=1$. But this follows by the induction hypothesis as long as $k+1\le 4k-4$, which is the case unless $k=1$, for which we can easily check each of the sums is nonnegative.

We proceed by strong induction. It is easy to see that the claim is true for $n=1,2,3,4,5,6,7,8$. We now induct modulo 4(with one of the cases split into two cases in modulo 8, the reason we needed to have 8 base cases). The two keys equations in this proof are $$x_{4k-3}=x_{2k-1}=-x_{4k-2}$$and $$x_{4k-1}=-x_{2k}=x_{4k}=x_k.$$Using these, we can finish the induction: Case 1: $n\equiv 0\pmod 4$ $\sum_{i=1}^{4k}x_i = \sum_{i=1}^k x_{4i-3}+x_{4i-2}+x_{4i-1}+x_{4i} = \sum_{i=1}^k x_{4i-1}+x_{4i}=2\sum_{i=1}^k x_{4i}=2\sum_{i=1}^k x_i\geq 0,$ where the last step follows from our induction hypothesis. Case 2: $n\equiv 3\pmod 4$ For convenience, instead of denoting $n$ as $4k+3$ we'll denote it as $4k-1$. Then $\sum_{i=1}^{4k-1} x_i = 2\sum_{i=1}^k x_i - x_{4k}=\sum_{i=1}^k x_i + \sum_{i=1}^k x_i-x_k=\sum_{i=1}^kx_i+\sum_{i=1}^{k-1}x_i\geq 0.$ Case 3: $n\equiv 2\pmod 4$. As in case 2, we denote $n$ by $4k-2$. Then $\sum_{i=1}^{4k-2}=2\sum_{i=1}^k x_i - x_{4k}-x_{4k-1}=2\sum_{i=1}^k x_i - 2x_k=2\sum_{i=1}^{k-1} x_i \geq 0$. Case 4: $n\equiv 1\pmod 4$ Case 4.a: $n\equiv 1\pmod 8$ In this case, we get that $\sum_{i=1}^{8k-7} = \sum_{i=1}^{8k-8} + x_{8k-7} = 2\sum_{i=1}^{2k-2}x_i+x_{2k-1}=\sum_{i=1}^{2k-2} x_i + \sum_{i=1}^{2k-1} x_i\geq 0.$ Case 4.b: $n\equiv 5\pmod 8$ In this case, we get that $\sum_{i=1}^{8k-3}x_i = \sum_{i=1}^{8k-4}x_i+x_{8k-3}=2\sum_{i=1}^{2k-1}x_i+x_{8k-3}(*)$. Notice that $2k-1$ is odd, which means that $2\sum_{i=1}^{2k-1} x_i\geq 2$ if it is positive, which it is by our induction hypothesis. Therefore $*\geq 1$. Because we have covered all possible cases, we are done by induction.

It is necessary to look at the smallest $n$, which is negative $x_1+x_2+...+x_n$, and then again at some $t$ smaller than this, the sum of $x_1+x_2+...+x_t$ will be less than 0.$t<n$

We will start by observing that, $$x_{4k+1}=x_{2(2k+1)-1}=x_{2k+1}=(-1)^{k+2}x_{k+1},\quad x_{4k+2}=-x_{2k+1}$$$$x_{4k+3}=x_{2(2k+2)-1}=-x_{2k+2}=x_{k+1},\quad x_{4(k+1)}=x_{k+1}$$We will prove the problem using strong induction on $n$,the base cases can be checked by hand.Suppose for all $k\le 4n$ we have, $$x_1+\dots+x_k\ge 0$$But then,using, $x_{4k+1}+x_{4k+2}=0,\forall k$ we have \begin{align*} \sum_{k=0}^n x_{4k+1}+x_{4k+2}+x_{4k+3}+x_{4k+4}&=\sum_{k=0}^n x_{4k+3}+x_{4k+4}=\sum_{k=0}^n 2x_{k+1}\ge 0 \end{align*}Also,$$x_1+\dots+x_{4n+2}=x_1+x_2+\dots+x_{4n}\ge 0$$ Hence it is enough to show the inequality for $4n+1,4n+3$.Observe that, $$x_1+\dots+x_{4n+1}=2(x_1+\dots+x_n)+x_{4n+1}=2(x_1+\dots+x_n)+(-1)^{n+2}x_{n+1}$$If $$2(x_1+\dots+x_n)\ge 2$$there is nothing to prove.If $2(x_1+\dots+x_n)=0$,then there is equal number of $1,-1$ among $x_1,\dots,x_n$.Hence $n$ is even.By our assumption ,$x_1+x_2+\dots+x_n+x_{n+1}\ge 0$ which shows $x_{n+1}=1$.So $$x_1+\dots+x_{4n+1}=2(x_1+\dots+x_n)+x_{4n+1}=2(x_1+\dots+x_n)+(-1)^{n+2}x_{n+1}=0+x_{n+1}=1$$ Finally,since $x_{4n+3}=x_{n+1}$, we have, $$x_1+\dots+x_{4n+2}+x_{4n+3}=2(x_1+\dots+x_n)+x_{n+1}$$Same argument of last paragraph shows the last sum is greater than 0.We are done $\blacksquare$

Lemma: $x_1+\ldots+x_{4n}=2(x_1+\ldots+x_{n})$. Proof: For all $k$, $x_{4k+1}+x_{4k+2}=((-1)^{2k+2}x_{2k+1})+(-x_{2k+1})=0$ and $x_{4k-1}+x_{4k}=((-1)^{2k+1}x_{2k})+(-x_{2k})=-2x_{2k}=2x_k$. So, $$x_{4k-3}+x_{4k-2}+x_{4k-1}+x_{4k}=2x_k$$$$x_1+x_2+\ldots+x_{4n}=2(x_1+x_2+\ldots+x_n)$$ We will prove the given statement using strong induction. If $n\equiv 0\pmod{4}$, then $$x_1+x_2+\ldots+x_n=2(x_1+x_2+\ldots+x_{\frac{n}4})\geq 0.$$If $n\equiv 2\pmod{4}$, then $$x_1+x_2+\ldots+x_n=x_1+x_2+\ldots+x_{n-2}=2(x_1+x_2+\ldots+x_{\frac{n-2}4})\geq 0.$$If $n\equiv 3\pmod{4}$, then $$x_n=x_{n+1}=-x_{\frac{n+1}2}$$$$x_1+x_2+\ldots+x_n=\frac{(x_1+x_2+\ldots+x_{n-1})+(x_1+x_2+\ldots+x_{n+1})}{2}=\frac{2(x_1+x_2+\ldots+x_{\frac{n-3}4})+2(x_1+x_2+\ldots+x_{\frac{n+1}4})}2\geq 0$$If $n\equiv 1\pmod{8}$, then $x_n=x_{\frac{n+3}4}$. So, $$x_1+x_2+\ldots+x_n=2(x_1+x_2+\ldots+x_{\frac{n-1}4})+x_{\frac{n+3}4}=(x_1+x_2+\ldots+x_\frac{n-1}4)+(x_1+x_2+\ldots+x_\frac{n+3}4)\geq 0.$$If $n\equiv 5\pmod{8}$, then $$x_1+x_2+\ldots +x_n=2(x_1+x_2+\ldots+x_{\frac{n-1}4})+x_n$$Since $\frac{n-1}4$ is odd, $x_1+x_2+\ldots +x_{\frac{n-1}4}$ is positive. So, $2(x_1+x_2+\ldots+x_{\frac{n-1}4})+x_n$ is nonnegative.

Solved with i3435 and L567. Let $S_k = \sum_{i=1}^{n} x_i$, we wish to prove that $S_n \geq 0$ for all $n \in \mathbb{N}$, we will use the following equations. \begin{align*} x_{4k+1} &= x_{2(2k+1) - 1} = (-1)^{2k+2} x_{2k+1} = x_{2(k+1)-1} = (-1)^k x_{k+1} \\ x_{4k+2} &= -x_{2k+1} = (-1)^{k+1} x_{k+1} \\ x_{4k+3} &= x_{2(2k+2)-1} = (-1)^{2k+3} x_{2k+2} = x_{k+1} \\ x_{4k+4} &= -x_{2k+2} = x_{k+1}. \end{align*} This gives us the most important observation in solving the problem: $$S_{4(k+1)} = \sum_{i=1}^{4(k+1)} x_i = S_{4k}+x_{4k+1}+x_{4k+2}+x_{4k+3}+x_{4k+4} = S_{4k}+2x_{k+1}$$then as $S_4 = 2 = 2S_1$, we have by induction that $S_{4k} = 2S_k$. Now, assume for the sake of contradiction that there exists some $n \in \mathbb{N}$ such that $S_n < 0$, and assume that $N$ is the smallest such positive integer, then $S_N = -1$ and $S_{N-1} = 0$, moreover, $N \equiv 1 \pmod{2}$ because $S_i \equiv i \pmod{2}$ for all $i \in \mathbb{N}$. We now have two cases. $\textbf{Case 1}$ $N-1 \equiv 2 \pmod{4}$ Let $N = 4k+3$ for some $k \in \mathbb{Z}_{\geq 0}$ and notice by the minimality of $N$ that $0 \leq 2S_{k+1} = S_{4k+4} = S_{4k+2}+x_{4k+3}+x_{4k+4} = 2 \cdot x_{4k+4}$ meaning that $x_{4k+4} \geq 1$, in fact, $x_{4k+4} = x_{4k+3} = 1$ but then $S_{4k+4} = S_{4k+2}+x_{4k+3} = 0+1 = 1 > 0$ meaning that $S_N \geq 0$ which is a contradiction. $\textbf{Case 2}$ $N-1 \equiv 0 \pmod{4}$ Let $N = 4k+1$ for some $k \in \mathbb{N}$ (as $S_1 =1 \geq 0)$. Then, firstly, $S_k = \frac{S_{4k}}{2} = 0$ meaning that $k$ is even because $0 \equiv S_k \equiv k \pmod{2}$ and also by the minimality of $N$, $x_{k+1} = 1$ because $0 \leq S_{k+1} = S_k+x_{k+1} = x_{k+1}$ means that $$x_{4k+1} = (-1)^k \cdot x_{k+1} = x_{k+1} = 1$$and hence $$S_{4k+1} = S_{4k}+x_{4k+1} = S_{4k}+1 = 1 \geq 0$$which again gives a contradiction. Having concluded both cases, which are exhaustive as $N \equiv 0 \pmod{2}$, we are done. $\blacksquare$

Divide the entire sequence into "2-blocks" which begin with an odd number and also "4-blocks" which begin with a $1 \pmod{4}$ number, so $x_5,x_6,x_7,x_8$ is a 4-block and $x_5,x_6$ is a 2-block. Also write $1$ as $+$ and $-1$ as $-$, so we would like to show that among the first $n$ terms of the sequence there is at least as many $+$ as $-$. Note that each 2-block will generate a unique 4-block. We will use a labeling system where the capital letter denotes the 4-block and the lowercase denotes the 2-block (so (a) denotes $++$): \begin{align*} ++ &\to +--- & (A)\\ +- &\to +-++ & (B)\\ -+ &\to -+-- & (C)\\ -- &\to -+++ & (D) \end{align*} Call a positive integer $n$ bad if either of the following conditions hold: Type 1: $x_1+\cdots+x_n<0$ Type 2: $n$ is even, and $x_2+x_4+\cdots+x_{n}>0$ We proceed with contradiction (basically strong induction). Pick $n$ minimal such that $n$ is bad. If $n$ is type 1, then write $n=4a+k$, with $1 \leq k \leq 4$. It is clear that we must have $x_1+\cdots+x_{4a}=0$, since each block either has sum $+2$ or $-2$, and we cannot make up a difference of $+2$ from taking the first few elements of any 4-block. Thus we must actually have $2 \mid a$, else the sum above is $2 \pmod{4}$. This leaves the following cases: $n=8m+4$ and $n$ is in an (A) or (C) block $n=8m+3$ and $n$ is in an (A) block $n=8m+1$ and $n$ is in a (C) or (D) block From the condition that $x_1+\cdots+x_{8m}=0$, by consulting the generation of 4-blocks we find that there the number of (A) and (C) blocks in the first $8m$ terms equals the number of (B) and (D) blocks, so in the first $4m$ terms the number of (a) and (c) blocks must equal the number of (b) and (d) blocks, i.e. $x_2+x_4+\cdots+x_{4m}=0$. Using this condition and again consulting the generation of 4-blocks, it follows that the first $4m$ terms contain equal numbers of (A) and (D) blocks, hence the first $2m$ terms contain equal numbers of (a) and (d) blocks and thus $x_1+\cdots+x_{2m}=0$. We then must have $x_{2m+1}=+$, otherwise $2m+1<n$ is bad, so then $x_{4m+1},x_{4m+2}$ is clearly a (b) block and $x_{8m+1},\ldots,x_{8m+4}$ is a (B) block. But none of the cases allow this: contradiction. Thus the minimal $n$ is type 2. It is clear that $x_2+x_4+\cdots+x_{n-2}=0$ and $x_n=+$. If $n/2-1$ is odd then there are an odd number of terms on the LHS, which is therefore odd. Thus $n/2-1$ is even, i.e. $n-2=4m$. Then as before we obtain $x_1+\cdots+x_{2m}=0$, hence $x_{2m+1}=+$ (otherwise $2m+1<n$ is bad), so $x_{4m+2}$ is in a (b) block and thus must be $-$, contradicting $x_2+x_4+\cdots+x_n>0$. From these two cases, it follows that a minimal $n$ cannot exist, so no positive integers are bad, and we are done. $\blacksquare$ Remark: There might be a few boundary issues if we take $n$ really small. They should be fixable by extending the definition of bad integers to $0$, which isn't bad, since empty sums are $0$. Alternatively, it is also possible to write out a couple of terms (I wrote down 32 before solving the problem) and checking that no $n \in [1,32]$ are bad, which makes the rest of the solution perfectly valid.

Let, $S_n = x_1 + x_2+\dots + x_n$   First, notice that, if $a \equiv b \pmod 2$ and $(x_a, x_{a+1}, \dots, x_{a+n}) = (x_b, x_{b+1}, \dots, x_{b+n})$,   Then, $(x_{2a-1}, x_{2a}, \dots, x_{2a+2n}) = (x_{2b-1}, x_{2b}, \dots, x_{2b+2n})$.   Using this by induction we can easily prove the fact that $(x_1, \dots, x_{2^k}) = (x_{2^{k+1}+1}, \dots, x_{2^{k+1}+2^k})$ and $(x_{2^k+1}, \dots, x_{2^{k+1}}) = (-x_{2^{k+1}+2^k+1}, \dots, -x_{2^{k+2}})$.    From this, we can also induct on power of $2$ to show that, $S_{2^{2k+1}} = 0$ and $S_{2^{2k}} = 2^k$ and $S_{2^{2k+1}+1} =1$ $\textbf{Claim 1:}$ For index $2^{2k-2} < d \leq 2^{2k}$, $S_d \geq 0$ where the first $0$ comes at $2^{2k-1}$ and $S_d \leq 2^k$ with exactly one equality case $d = 2^{2k}$   $\underline{\text{Proof:}}$ We prove it by induction. Base cases are trivial to check. Assume that this is true for $k = n$.   FTSOC, let's assume that this isn't true for $k = n+1$. Then there must be some index $2^n < d < 2^{2n+2}$ for which $S_d = 2^{n+1}$ or $S_d < 0$ or some $S_d = 0$ with $d < 2^{2n+1}$     Then there are some cases.   $\textbf{Case 1:}$ $2^{2n} < d \leq 2^{2n} + 2^{2n-1}$   In this case,  we get, $S_{d - 2^{2n}} = 2^n$ or $S_{d - 2^{2n}} < -2^n$ or $S_{d - 2^{2n}} = -2^n$. which contradicts our hypothesis.   $\textbf{Case 2:}$ $2^{2n} + 2^{2n-1} < d \leq 2^{2n+1}$   In this case, we get, $S_{d-2^{2n}} = -2^n$ or $S_{d-2^{2n}} > 2^n$ or $S_{d-2^{2n}} = 2^n$ and again all contradicts unless $d = 2^{2n+1}$.   And by this we already proved that the first zero comes at $d = 2^{2k+1}$   $\textbf{Case 3:}$ $2^{2n+1} < d \leq 2^{2n+1} + 2^{2n}$    In this case we get, $S_{d-2^{2n+1}} = 2^{n+1}$ or $S_{d-2^{2n+1}} < 0$. Again clearly contradicts with Case 1,2 and hypothisis.   $\textbf{Case 4:}$ $2^{2n+1} + 2^{2n} < d \leq 2^{2n+2}$    In this case, we get $S_{d - 2^{2n+1}} =0$ or $S_{d - 2^{2n+1}} > 2^{n+1}$ both we proved in Case 1,2 that can't happen.   And these were all the cases. So we are done. $\blacksquare$

Note that $x_{4k-3}=x_{2k-1}$, $x_{4k-2}=-x_{2k-1}$, $x_{4k-1}=-x_{2k}=x_k$, $x_{4k}=-x_{2k}=x_k$. Let $S_k$ denote $x_1+x_2+\dots+x_k$, then \[S_{4k}=\sum_{i=1}^{k}{x_{4k-3}+x_{4k-2}+x_{4k-1}+x_{4k}}=\sum_{i=1}^{k}{2x_k}=2S_k\]and since $x_{4k-3}+x_{4k-2}=0$, $S_{4k+2}=S_{4k}$. We show by induction on $k$ that $S_{4k-3}$, $S_{4k-2}$, $S_{4k-1}$, and $S_{4k}$ are all nonnegative. Base cases are obvious. Suppose it's true for $k=i-1$. Then, let $k=i$. We have $S_{4k-2}$ and $S_{4k}$ are clearly nonnegative. Note that $S_{4k-2}, S_{4k-1}, S_{4k}$ forms an arithmetic sequence with common difference $x_k$, so $S_{4k-1}$ is also nonnegative. It remains to show that $S_{4k-3}$ is nonnegative. If $k$ is odd, then \[S_{4k-3}=S_{4k-4}+x_{2k-1}=2S_{k-1}+x_{k}=S_{k-1}+S_k\ge 0\]and if $k$ is even, then \[2S_{k-1}+x_k\ge 1\]because $S_{k-1}$ is a sum of odd number of odd terms, so it is odd and nonnegative, implying it is at least one.

i hate induction because of this problem its just a bunch of random inductive patching arguments We proceed by induction; check manually the base cases 1,2,3,4, and let $s_n=x_1+s_2+\ldots+x_n$; we'll prove that s_n is nonnegative always, so assume it's true for all k=n. It's obvious $$(x_{4n+1},x_{4n+2},x_{4n+3},x_{4n+4})=(x_{2n+1},-x_{2n+1},-x_{2n+2},-x_{2n+2})=(x_{2n+1},-x_{2n+1},x_{n+1},x_{n+1})\implies s_{4n}=\sum_{i=0}^{n-1}x_{4i+1}+x_{4i+2}x_{4i+3}+x_{4i+4}=\sum_{i=0}^{n-1}2x_{i+1}=2s_n;$$in particular, because $s_{4n+2}=s_{4n}$, which is clearly nonnegative by inductive hypothesis and our derived equation; $s_{4n+4}-s_{4n+3}=s_{4n+3}-s_{4n+2}=x_{2n+1}\implies s_{4n+3}\ge 0$. To finish, for indices 1 mod 4, $$n=2m+1\implies s_{4n+5}=s_{4n+4}+x_{2n+3}=2s_{n+1}+x_{n+2}=s_{n+1}+s_{n+2}\ge 0,n=2m\stackrel{s_{n-1}\ge 0}{\implies}2s_{n-1}+x_n\ge s_{n-1}+x_n=s_n\ge 0,$$as desired. $\blacksquare$ but oops i just realized i just solved an a3 and a4 and got no sense of accomplishment whatsoever i guess thats what happens as you get more experience this stuff just becomes standard

Let $s_n=x_1+x_2+\dots+x_n$. Claim: $s_{2n}=2s_{\lfloor n/2 \rfloor}$ for $n\geq 2$. Proof. Note that \begin{align*} s_{2n} & = \sum_{i=1}^n (x_{2i-1}+x_{2i}) = \sum_{i=1}^n \left ((-1)^{i+1}x_i-x_i\right ) = -\sum_{i=1}^n x_i \left (1+(-1)^i\right ) \\ & = -2\sum_{i=1}^{\lfloor n/2\rfloor} x_{2i} = 2 \sum_{i=1}^{\lfloor n/2\rfloor} x_i = 2s_{\lfloor n/2\rfloor}. \end{align*} Suppose that we have proven that $s_1, s_2, \dots, s_{2k} \geq 0$. By the claim, $s_{2k+2} \geq 0$. Hence it suffices to prove $s_{2k+1} \geq 0$. This will complete the proof via induction. Assume that $s_{2k+1}<0$. We must have $s_{2k}=0$, $x_{2k+1}=-1$ and $x_{2k+2}=1$. This implies $x_{k+1}=-1$ and $$-1=x_{2k+1}=(-1)^{k+2}x_{k+1}=-(-1)^k \implies k=2m, \ (m \in \mathbb N)$$Note that $0=s_{2k}=2s_m$. So, $$x_{m+1}=x_{m+1}+s_m=s_{m+1} \geq 0 \implies x_{m+1}=1.$$So, $$(-1)^m=x_{m+1}(-1)^{m+2}=x_{2m+1}=x_{k+1}=-1$$which implies that $m$ is odd. Note that $s_{m+1}=1$, which is a contradiction since $m+1$ is even and as such $s_{m+1}$ must be even (due to the claim).

Suppose not, and fix $n$ so that $n$ is the smallest for which this is not true. For any positive integer $m$, let $s_m = x_1 + x_2 + \cdots + x_m$. Note that $s_n < 0$. Note that\begin{align*} x_{4k} = -x_{2k} = x_k \\ x_{4k + 1} = x_{2(2k + 1) - 1} = x_{2k + 1} = (-1)^{k} x_{k + 1} \\ x_{4k + 2} = - x_{2k + 1} = - x_{4k + 1} \\ x_{4k + 3} = x_{2(2k + 2) - 1} = -x_{2k + 2} = x_{4k + 4} = x_{k + 1} \\ x_{4k + 4} = x_{k + 1} \\ \end{align*}So $ x_{4k + 1} + x_{4k + 2} + x_{4k +3} + x_{4k + 4} = 2x_{k + 1}$. Now if $n \in [4t, 4t + 3]$, we have\[s_n = \sum_{i=0}^{t - 1} (x_{4i + 1} + x_{4i + 2} + x_{4i + 3} + x_{4i + 4}) + \sum_{i=4t + 1}^n x_i = 2s_t + \sum_{i = 4t + 1}^n x_i \ge \sum_{i=4t + 1} ^n x_i \]Let $N = \sum_{i = 4t + 1}^n x_i$. We have $s_n \ge N$, so $N$ is negative. Additionally, note that $s_m = 0 \forall m \in \{1, 2, 3\}$, so $t > 0$. First note that $N$ is either $0, (-1)^{k + 1} x_k, $ or $x_{k + 1}$, so it's at least $-1$. But since the LHS of the inequality chain is at most $-1$, everything in the inequality chain must equal $-1$. Thus,\[ 2s_t +N = 0 \implies 2s_t = 0 \implies s_t = 0 \]Since $s_t$ and $t$ have the same parity, $t$ is even. If $n = 4t$, then we have $N = 0$, which is a contradiction since $N$ should be negative. If $n = 4t + 1$, then $N = x_{4t + 1} = x_{2t + 1} = (-1)^{t + 1} x_t = -x_t$. Since $N$ is negative, $x_t = 1$, so $s_{t - 1} = s_t - 1$ is negative, a contradiction. If $n = 4t + 2$, then we have $s_n = s_{4t} + x_{4t + 1} + x_{4t + 2} = s_{4t} \ge 0$, absurd. If $n = 4t + 3$, then $N = x_{4t + 1} + x_{4t + 2} + x_{4t + 3} = x_{4t + 3} = x_{t + 1}$. Now, this implies $x_{t+1}$ is negative, but since $s_t = 0$, $s_{t + 1} = s_t + x_{t+1}$ is negative, a contradiction. Hence $n$ cannot exist, so $x_1 + x_2 + \cdots + x_n \ge 0 \forall n \in \mathbb N $.