0
$\begingroup$

I am reading Steven Skiena's Algorithm Design Manual, trying to review summation in chapter 1.3.5.

Skiena states "The sum of the first n integers can be seen by pairing up the ith and (ni + 1)th integers" and then shows the following two summations and equation as being equal:

$$\sum_{i=1}^n i = \sum_{i=1}^{n/2} i+(n-i+1) = n(n+1)/2$$

I understand that $\sum_{i=1}^n i$ = $n(n+1)/2$ (though not how it was derived)

What I don't understand is how $\sum_{i=1}^n i$ = $\sum_{i=1}^{n/2} i+(n-i+1)$ or what Skiena means in his statement of pairing up integers.

Inputting any even number gives the correct result, but odd numbers don't seem to produce the correct result due to the upper bound not being a whole number. Skiena does not mention any rounding or truncating.

I am not sure how to work with a summation that contains an upper bound that is not a whole number, so I suspect that may be the root cause.

My question is, why are these two summations equal?

$\endgroup$
1
  • $\begingroup$ Is it true when $n=6$? That is: $1+2+3+4+5+6 = (1+6)+(2+5)+(3+4)$. Once you understand that this is what your equation says in case $n=6$, can you see how to do it for general even $n$. Skiena should have assumed $n$ is even. $\endgroup$
    – GEdgar
    Apr 5 '20 at 20:32
1
$\begingroup$

What he’s written is sloppy, since it does not take into account the case of odd $n$. Probably the easiest way to do it is to start with the observation that $\sum_{i=1}^ni=\sum_{i=1}^n(n+1-i)$, since the second sum just runs through the integers $1,\ldots,n$ in reverse order. Then

$$\begin{align*} 2\sum_{i=1}^ni&=\sum_{i=1}^ni+\sum_{i=1}^n(n+1-i)\\ &=\sum_{i=1}^n\big(i+(n+1-i)\big)\\ &=\sum_{i=1}^n(n+1)\\ &=n(n+1)\;, \end{align*}$$

and dividing by $2$ yields the familiar formula.

$\endgroup$
0
$\begingroup$

See https://www.nctm.org/Publications/Teaching-Children-Mathematics/Blog/The-Story-of-Gauss/ . The picture starting off is "pairing up the ith and (n − i + 1)th integers".

There should be a special step for when the length of the sum is odd, since the term "in the middle" has no pair. When you account for that unpaired term in the middle sum, you still get the expression on the right.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.