# Find the smallest possible value of the sum $x_1+x_2+…+x_{2008}$

Let $$x_1, x_2,...,x_{2008}$$ are numbers such that $$|x_1|=999$$ and for all $$n=2,...,2008$$
$$|x_n|=|x_{n-1}+1|$$ Find the smallest possible value of the sum
$$x_1+x_2+...+x_{2008}$$

### My work:

Let $$S=x_1+x_2+...+x_{2008}$$.

If $$x_1=-999, x_2=-998, ..., -1,0,-1,0$$ then I think the answer $$-500004$$.

But I don't know how to prove that:

• Finding the smallest possible value of $|x_1+x_2+\cdots+x_{2008}|$ is also an interesting problem. (In fact, it's how I interpreted the problem on first reading.) – TonyK Jan 16 '19 at 12:58
• The minimization problem can be understood as a multi-staging process in which the transition to a new staging, from $\sum_{k=1}^N x_k$ to $\sum_{k=1}^{N+1} x_k$ is constrained by the condition $|x_{k+1}| = |x_k+1|$ so the procedure to solve it can be successfully handled with a Dynamic Programming algorithm. – Cesareo Jan 17 '19 at 11:04
• On a side note, @Roman, let me ask you this: aren't you going to create an OEIS entry for the sequence from math.stackexchange.com/questions/2469058/…? IMHO, it more than deserves one. – Ivan Neretin Jan 17 '19 at 22:46
• @IvanNeretin: No! I do not know how do it. But if you want you will can do it. – Roman83 Jan 18 '19 at 8:08
• @Roman So I will. May I know your full name, at least? I don't want to claim it in my name, as the idea is yours. – Ivan Neretin Jan 18 '19 at 8:39

$$S_1(x_1) = \{-m,m\}$$
$$S_k(x_k) = \min_{x_k}\left(S_{k-1}(x_{k-1})+x_k\right)\ \ \mbox{s. t. }\ \ |x_k|=|x_{k-1}+1|$$
we have after $$N$$ steps the sought min as $$\min S_N(x_N)$$