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

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

I was wondering about this problem and didn't think it was immediately obvious. The answer can't be $2^{n-1}$ since the combinations all might not be unique. I was thinking of looking at partitions of $\{1,2,\ldots,n, k\}$ where $1 \pm 2 \pm 3 \pm \cdots \pm n = k$ and thus the sum must be even. Therefore, $\dfrac{n(n+1)}{2}+k = \dfrac{n(n+1)+2k}{2}$ must be even which means $n(n+1) + 2k$ must be a multiple of $4$ so $n(n+1)+2k = 4m$. Thus if $n \equiv 1,2 \bmod 4$, then $k \equiv 1,3 \bmod 4$ and if $n \equiv 3,0 \bmod 4$ then $k \equiv 0,2 \bmod 4$.

• @ObinnaNwakwue it's at the top in a box – Stella Biderman Apr 30 '16 at 15:10
• The problem is that not all values of $k$ are obtainable. – user19405892 Apr 30 '16 at 15:12
• Well, everyone else has answered it but: a)all values are between n (n+1)/2 and -n (n+1)/2 +2. b) then numbers are precisely n(n+1)/2 - 2k where k is a number that is a sum of 0 or more distinct terms, 0,1,2....n. (so all values are the same parity) and c) it's easy to show every number between 0 and n (n+1)/2 can be written as a sum of 0 or more distinct terms between 0 and n. Ergo: the solutions are precisely all the terms between -n (n+1)/2 and n (n+1)/2 of the same parity. a) b) and c) each have to be shown but they are each straightforward. – fleablood Apr 30 '16 at 19:32
• See a rather similar similar question here. – Jean Marie Apr 23 '17 at 16:00

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.

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 .

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?

• How does that help? – user19405892 Apr 30 '16 at 15:26
• I think it gives the answer. How many (and which) integers can you get by adding some of the elements from $\{2,3,4,\ldots,n\}$? Double them and subtract them from $\frac{n(n+1)}{2}$. – Jack D'Aurizio Apr 30 '16 at 15:27
• You can get $5,6,\ldots,2n-1$. Thus there are $2n-5$ possible values? – user19405892 Apr 30 '16 at 15:32

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$$

• This gives a very pleasing intuition about why the elements at the "maximum minus 2" and "minimum plus 2" are missing when we force the sign of the term 1 to be positive. – David K Feb 7 '17 at 15:49