4
$\begingroup$

Possible Duplicate:
What is the term for a factorial type operation, but with summation instead of products?

I got this question in homework:

Find an expression for the sum ‫‪

$\sum k = 1 +\cdots + n‬‬$.

and prove it using an induction.

I'm not even near finding the expression. What I did notice is that if $n$ is (for example) 5 then the sum would be

$5^2 - 4^2 + 3^2 - 2^2 + 1^2$

So the first number is always positive and from there on the sign changes.

Any tips on how do I contintue from this point on, assuming I'm in the right direction?

Thanks!

  • 0
    maybe [this](https://nrich.maths.org/discus/messages/145082/146345.html?1242224412) could be helpful2011-11-04
  • 0
    @yotamoo: This is a very nice observation that can be used to find the summation formula for the squares starting from the summation formula you are trying to prove at the moment.2011-11-04

2 Answers 2

10

Hint. $$\begin{array}{cccccccccccc} & 1 & + & 2 & + & 3 & + & 4 & + & \cdots & + & n\\ +& n & + &n-1 & + & n-2 & + & n-3 & + & \cdots & + & 1\\ \hline & n+1 & + &n+1 & + &n+1 &+& n+1 & + & \cdots & + & n+1 \end{array}$$

  • 0
    To expand on this, if n is even, how many instances of (n+1) do we have here?2011-11-04
  • 3
    @Doug You do not need $n$ to be even for this answer. There are always $n$ occurrences of $(n+1)$ in the last line, odd or even.2011-11-04
  • 3
    @all: This is often called Gauss' trick.2011-11-04
  • 0
    I love this trick -- usually blows the mind of at least one student when shown to them. Can you do something similar for the sum of squares, cubes, etc?2011-11-04
  • 0
    @Srivatsan Huh? If n=4, then we have 1+2+3+4, so we have 4+1, and 4+1 in the last line. So, we have *2* occurrences of (n+1) in the last line. If n=5, then we have 1+2+3+4+5, so we have 4+1, 4+1, and 3 for *2* occurrences of (n+1) in the last line. You're right n doesn't need to be even for this answer, but the question I asked seems simpler to answer if you only consider the even cases.2011-11-04
  • 0
    @MikeWierzbicki Consider 1+4+9+16. So, we have ((1+16)+(4+9)). 1+16 doesn't equal 4+9, so we know from this, that if something exists here, this isn't quite so simple.2011-11-04
  • 0
    @Doug: Nonsense: if $n=4$, then we have *four* occurrences of $4+1$ in the last line, not two. If $n=5$, we have *five* occurrences of $n+1$ in the last line, not "2 ocurrences of n+1 and [one of $3$] in the last line". If n=6, then we have *six* occurrences of $n+1$ in the last line. *You* are doing something else: you are pairing the first term with the last, the second with the penultimate, and so on, which drops you into cases. But *that* is not what "we have here" (i.e., in my answer), where I am considering two copies of the sum we are looking for, not one.2011-11-04
  • 0
    @ArturoMagidin With your hint then, you're trying to find 2(1+...+n) before finding (1+...+n) which is fine. I was thinking more directly. If you want to find 1+...+200, you just notice we have (1+200)+(2+199)+...+(99+100)=201+201+...+201, which is more along the lines of the Gauss story than your hint, where he supposedly tries to find 1+...+100 without finding their double first. My mistake.2011-11-04
  • 0
    @Doug: No instance of the Gauss story that I am aware of says *how* he obtained the formula, only that he figured it out or knew it. Certainly, since it's a story told later by someone else, we don't know how Gauss figured it out (if it did indeed happen). So I'm not sure how one could say that one method is "more along the lines of the Gauss story" than another.2011-11-04
  • 0
    @MikeWierzbicki: For sums of squares, cubes, etc., it makes more sense to use the method of GarouDan's answer. See also Bill Dubuque's answer [here](http://math.stackexchange.com/questions/72660/having-problem-in-mathematical-induction/72668#72668).2011-11-04
  • 0
    @ArturoMagidin The wikipedia on Gauss says "Gauss's presumed method was to realize that pairwise addition of terms from opposite ends of the list yielded identical intermediate sums: 1 + 100 = 101, 2 + 99 = 101, 3 + 98 = 101, and so on, for a total sum of 50 × 101 = 5050." So, I can say that, since the story (not Gauss's actual thinking) sometimes segues into an explanation like that, such as here http://www.jimloy.com/algebra/gauss.htm. You're also pairing the first term with the last, the second with the penultimate and so on, but each pairing happens twice for you2011-11-04
  • 0
    @Doug: That quote is under "Mythology"; the only [source cited](http://www.americanscientist.org/issues/pub/gausss-day-of-reckoning/2) says explicitly of the first known instance of the story (1856): "What's most remarkable about the Sartorius telling of the story is not what's there but what's absent. There is no mention of the numbers from 1 to 100, or any other specific arithmetic progression. And there is no hint of the trick or technique that Gauss invented to solve the problem; the idea of combining the numbers in pairs is not discussed, nor is the formula for summing a series."2011-11-04
  • 0
    @ArturoMagidin Edit: that should go that you've paired the first term with the last, the second with penultimate, and so on, except, if it exists, the exact middle term which you've paired with itself once, while I haven't paired it with anything, or duplicated pairs.2011-11-04
4

Hint:

If $S_n$ is your sum $S_n=1+2+3+\ldots+n$

then, it's simple you see that

$S_{n}-S_{n-1}=(1+2+\ldots+n-1+n)-(1+2+\ldots+n-1)=$

$(1-1)+(2-2)+\ldots+(n-1 -(n-1))+n=n$.

Now you can use a trick, you can think $S_n$ is a polynomial of degree 2, so

$S_n=an^2+bn+c$

Putting this in the equation

$S_n-S_{n-1}=n$, you will find $a$, $b$ and $c$ and then, you get your sum or $S_n=an^2+bn+c=1+2+3+\ldots+n$.

This is more general, but @ArturoMagidin ways is the easiest.