1

I was solving a practice competitive programming question when I realized that this seems very familiar to the things I have done in a Calculus class. So, I tried to figure out the closed form partial sum for $\sum _{ n=1 }^{ m }{ (-1)^{ n }\cdot n } $, but I realized that I am in over my head. I entered "$-1 + 2 + -3 + 4 + -5 +...$" into Wolfram Alpha, and I got that the partial sum formula for $\sum _{ n=1 }^{ m }{ (-1)^{ n }\cdot n } = \frac { 1 }{ 4 } (2(-1)^{ m }m+(-1)^{ m }-1)$

I feel guilty for blindly applying a formula to solve a problem, and I have not been able to find any wikipedia article, or any other source that provides an explanation for this closed form partial sum formula. I would appreciate if someone can provide an explanation for this.

Cherry_Developer
  • 4,239

4 Answers4

3

You are computing the sum of the even numbers minus that of the odd numbers.

Assuming $m=2k+1$,

$$\sum_{n=0}^k2k-\sum_{n=0}^k(2k+1)=\sum_{n=0}^k(2k-(2k+1))=-\sum_{n=0}^k1=-k-1.$$

Or assuming $m=2k$, undo the last odd term and get

$$-k-1+2k+1=k.$$

To get a closed formula, notice that

$$m=2k\to S=\frac m2,\\ m=2k+1\to S=-\frac{m+1}2,$$

which can be summarized as

$$(-1)^m\frac{m+\dfrac{1-(-1)^m}2}2$$ or

$$(-1)^m\frac{m+m\bmod2}2.$$

3

When faced with such a problem compute the partial sums $s_n$ for small $n$, and hope you can detect a pattern, like so: $$\matrix{n:&1&2&3&4&5&6&7&8&9&10&\ldots\cr s_n:&-1&1&-2&2&-3&3&-4&4&-5&5&\ldots\cr}$$ Looking at these figures one immediately recognizes the law $$s_n=(-1)^n\left\lceil{n\over2}\right\rceil\ ,$$ whereby a formal induction proof could easily be supplied if desired.

Christian Blatter
  • 226,825
1

HINT: It will help to write some base cases. We have $f(1)=-1, f(2) =1, f(3)=-2,...$. To write the formula for $f(n)$, we can divide it into two base cases:
$(1)$ If $n$ is even, we can write $f(2n) = -(1+3+5+\cdots+(n-1)) + (2+4+\cdots +2n) = -n^2 + 2\frac{n(n+1)}{2} = n$.
$(2)$ If $n$ is odd, we can similarly write $f(2n+1) = -(n+1)$.

Can you now try writing a closed form partial sum representation?

1

One approach: start more general than you need to, and then specialise:

  • Let $f_n(x)=x+2x^2+\cdots+nx^n$
  • Then, $(1-x)f_n(x)=(x+2x^2+\cdots+nx^n)-(x^2+2x^3+\cdots+nx^{n+1})$
  • Cancelling out, $(1-x)f_n(x)=x+x^2+\cdots x^n-nx^{n+1}$
  • Applying the same trick again, $(1-x)^2f_n(x)=x(1-x^n)-nx^{n+1}(1-x)$

Now, you're looking for $f_n(-1)$, so we plug this into the final expression here to see:

$$4f_n(-1)=(-1)(1-(-1)^n)-n(-1)^{n+1}(2)$$

and cleaning up this expression gives the sum you mention.

πr8
  • 10,800