IMO 2010 — Complete Shortlist Question 4

A sequence $x_{1}, x_{2}, \ldots$ is defined by $x_{1}=1$ and $x_{2 k}=-x_{k}, x_{2 k-1}=(-1)^{k+1} x_{k}$ for all $k \geq 1$. Prove that $x_{1}+x_{2}+\cdots+x_{n} \geq 0$ for all $n \geq 1$.