How many values does the expression $1 \pm 2 \pm 3 \pm \cdots \pm n$ take?

Solution 1:

To start with, you can forget about the leading term, $1$. All that term does is to shift all the values one place to the right on the number line. The expression $\pm 2 \pm 3 \pm \cdots \pm n$ has the same number of distinct values as $1 \pm 2 \pm 3 \pm \cdots \pm n$.

From this point until further notice, I'll consider only sums of the form $\pm 2 \pm 3 \pm \cdots \pm n$.

All possible sums have the same parity.

The minimum sum is $\sum_{i=2}^n(-i) = -\frac{(n+2)(n-1)}{2}$, when all the $\pm$ signs are negative. The sum $-\frac{(n+2)(n-1)}{2} + 2$ is clearly not achievable, but $-\frac{(n+2)(n-1)}{2} + 4$ is, as long as $n \geq 2$.

Now as long as the sum includes two terms $j - (j+1)$ (positive followed by negative), we can change the two terms to $-j + (j+1)$ and thereby increase the sum by $2$.

If there are no such terms, that is, all the negative terms occur before any of the positive terms, the sum has the form $$-2 - 3 - \ldots - (j-1) - j + (j+1) + \ldots + n = k \tag1$$ where $1 \leq j \leq n$. (In the case $j = 1$, all terms are positive.)

We have already considered the case $j = n$. In the case $j=1$, the sum has the maximum value, $\frac{(n+2)(n-1)}{2}$, and in the case $j=2$, the sum has the second greatest possible value, $\frac{(n+2)(n-1)}{2} - 4$. Now suppose instead that $3 \leq j \leq n-1$. Then we can change the sum on line $(1)$ to $$2 - 3 - \ldots - (j-1) + j - (j+1) + \ldots + n = k + 2.$$

In other words, if $n > 3$, then except for the values $-\frac{(n+2)(n-1)}{2}$, $\frac{(n+2)(n-1)}{2} - 4$, and $\frac{(n+2)(n-1)}{2}$, every possible value of the sum (including $-\frac{(n+2)(n-1)}{2} + 4$) corresponds to another sum that is greater by $2$. So the possible sums are $-\frac{(n+2)(n-1)}{2}$, $\frac{(n+2)(n-1)}{2}$, and every integer of the same parity from $-\frac{(n+2)(n-1)}{2} + 4$ to $\frac{(n+2)(n-1)}{2} - 4$, inclusive.

The number of integers in $\left[-\frac{(n+2)(n-1)}{2}, \frac{(n+2)(n-1)}{2}\right]$ is $(n+2)(n-1) + 1$, and those of the same parity are $\frac{(n+2)(n-1)}{2} + 1$. So if $n > 3$, the total number of possible sums (excluding the values $-\frac{(n+2)(n-1)}{2}+2$ and $\frac{(n+2)(n-1)}{2}-2$, which are not possible sums) is $$\left(\frac{(n+2)(n-1)}{2} + 1\right) - 2 = \frac12(n^2 + n - 4).$$

For example, if $n=4$ then there are $8$ possible sums: $-9,-5,-3,-1,1,3,5$, and $9$.

By inspection, this formula also gives the number of sums for $n=3$ (the sums are $-5,-1,1,$ and $5$), but the number of sums for $n=2$ is $2$, which does not agree with the formula; $n=2$ must be treated as a special case.

If you modify the original expression by making the first term $\pm1$, that is, if you consider $\pm 1 \pm 2 \pm \cdots \pm n$, the minimum is $-\frac{n(n+1)}{2}$, the maximum is $\frac{n(n+1)}{2}$, and all integers of the same parity between those values are possible sums.

Solution 2:

Let us use generating functions

$$G_n(X)=X\prod_{k=2}^n(X^{-k}+X^k)=\dfrac{1}{X^p}\prod_{k=2}^n(1+X^{2k}) \ \ \ \text{with} \ \ \ p=\frac{n(n+1)}{2}-2$$ (very close to the proposal of @Jack D'Aurizio). In this way, we transfer the issue into counting how many combinations as positive or negative exponents of indeterminate $X$ are present in the expansion of $G_n(X)$.

Let us manipulate the first values of $n$ which is enough to get a good perception of the method.

We begin by the case $n=3$:

$$G_3(X)=X(X^{-2} + X^2)(X^{-3} + X^3)=$$ $$X^{1-2-3} + X^{1+2-3} + X^{1-2+3} +X^{1+2+3}$$ $$=X^{-4} + X^0 + X^2 + X^6$$

Note the central symmetry (with respect to position $1$) of the exponents $-4,0,2,6$. This central symmetry will exist for all values of $n$.

Let us now consider the cases $n=4, 5, 6$:

$n=4$:

$$G_4(X)=X(X^{-2} + X^2)(X^{-3} + X^3)(X^{-4} + X^4) =$$ $$X^{-8} + X^{-4} + X^{-2} + X^0+ X^2 + X^4 + X^6 + X^{10}$$

Till now, there are no repetitions. Here they come for $n \geq 5$:

$n=5$:

$$G_5(X)=X(X^{-2} + X^2)(X^{-3} + X^3)(X^{-4} + X^4)(X^{-5} + X^5)$$ $$=X^{-13} + X^{-9} + X^{-7} + X^{-5} + 2X^{-3} + X^{-1} + 2\,X + X^3 + 2\,X^5 + X^7 + X^9 + X^{11} + X^{15}$$

This time, not all coefficients are one; the reason is clear: for example, monomial $^2X^5$ means that $5$ is obtainable in two ways, i.e., $1+2+3+4-5$ and $1-2-3+4+5$. This is an "added value" of the approach by generating functions.

A last case, $n=6$, in order to see the differences between the cases $n$ odd and $n$ even:

$$X(X^{-2} + X^2) \cdots (X^{-5} + X^5)(X^{-6} + X^6)=$$ $$=X^{-19} + X^{-15} + X^{-13} + X^{-11} + 2X^{-9} + 2X^{-7} + 2X^{-5} + 2X^{-3} + 3X^{-1} + 2\,X + 3\,X^3 + 2\,X^5 + 2\,X^7 + 2\,X^9 + 2\,X^{11} + X^{13} + X^{15} + X^{17} + X^{21}$$

I will not go beyond this point because there is a clear recurrence relationship, but developing it would look to the reader like paraphrasing the (very detailed) redaction of @David K .

Solution 3:

Hint: $$ 1\pm 2\pm 3\pm 4\ldots \pm n = \frac{n(n+1)}{2}-a_2-a_3-\ldots-a_n, \qquad a_k\in\{0,2k\}.$$ Consider $(1+x^4)(1+x^6)\cdot\ldots\cdot(1+x^{2n})$. How many monomials appear in the expansion?

Solution 4:

In a similar, but newer question here in MSE I gave a "proof without words" (however, I needed a couple of words to explain the picture).

Here is a similar picture; if you have read the explanations in that other thread once, you never need this anymore...

It means, we begin with the set-of-result $R_0 = \{0\}$ having cardinality $ \# R_0=1$ .

Then we initialize a set of summands, $S_1=\{1\}$ . To each element in $R_0$ we add the new summand $s_1=1$ getting a new results-set $R_1 = \{1\}$. Its cardinality is $\#R_1=1$ . In the picture this is reflected by the top-most green arrow for addition; because we do not use $-1$ the subtraction-arrow is grey and the subtraction-value $-1$ is not a valid element in $R_1$

After that we add the element $s_2=2$ to our summands-set. We arrive at the new results-set $R_2$ by adding (green arrows) and subtracting (red arrows) that $s_2$ to each element in $R_1$.

And so on. In the picture I've documented in grey the missing elements compared with the symmetric tree, when the first summand were $ \pm 1$ in the problem definition instead of only $+1$ .

But the evolution of the iteration becomes immediately clear after seeing $R_4$ and $R_5$. In each new row shall 3 elements be invalid/missing compared with the symmetric tree as shown in the other answer. The formula for the cardinalities can simply be derived to be (for $ k \ge 3$): $$ \# R_k = \binom{1+k}{2} -2 $$