How was $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$ calculated? [duplicate]

I know how to prove $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$ works by mathematical induction, but how was the algorithm created?

Was it just trial and error?

How is any generic equation like this created with summation? At what level of math would I actually start learning how to come up with these equations myself?

-

marked as duplicate by Aryabhata, ShreevatsaR, Chandru, Ross Millikan, Américo TavaresJul 22 '11 at 17:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

I think this question (or some question whose answers answer this question) has been asked before on this website, but I can't find it right now… – ShreevatsaR Jul 22 '11 at 17:04
See also here math.stackexchange.com/questions/50485/… – leonbloy Jul 22 '11 at 17:09
@Oghma: Look at Bill's answer. That shows you how to come up with it... – Aryabhata Jul 22 '11 at 17:10
@Oghma: See this article Gauss's Day of Reckoning and also this collection for a list of tellings of the story of how one person (Gauss) came up with it. Of course, the formula was known earlier than Gauss, but it's something that many people rediscover so these accounts ought to be satisfying. :-) – ShreevatsaR Jul 22 '11 at 17:15
@Oghma: Oh, for the question "At what level of math would I actually start learning how to come up with these equations myself", one answer is that you can come up with some of these equations after reading the first couple or so chapters of the great book Concrete Mathematics by Graham, Knuth and Patashnik. – ShreevatsaR Jul 22 '11 at 17:17

2 Answers

A standard way of "discovering" this formula is to take the sum twice, in opposite order: $$\begin{array}{ccccccccc} 1 & + & 2 & + & 3 & + & \cdots & + & n\\ n & + & n-1 & + & n-2 & + & \cdots & + & 1\\ \hline (n+1) & + & (n+1) & + & (n+1) & + & \cdots & + & (n+1) \end{array}$$ which readily yields that twice the sum equals $(n+1)n$, from which the result follows.

This kind of insight might strike "as a bolt from the blue" easily enough.

More interesting, perhaps, is to ask about more general formulas for sums of powers, $$\sum_{i=1}^n i^k$$ with $k$ a positive integer. There are many systematic ways for finding such formulas; see for example this paper, or this Monthly paper by Beardon to get started.

-

Actually this one formula has many beautiful and different ways of being deduced. It probably also has been asked a few times before on this website? The way most people first see, along with the story of the young Gauss figuring it out when he was 11 years-old or something.

It goes like this : First, write the sum of the first $n$ integers, once forwards and once backwards. $1+2+3+4+5+...+n$

$n+(n-1)+(n-2)+(n-3)+...+1$

it is not too hard to see that if you sum together one number from the top row with one number from the bottom row you will always get the result $n+1$, but then you will be summing everything twice, which means that the total sum is $n(n+1)/2$.

As far as I know there isn't really a "general" way of finding formulas for arbitrary sums, the strategies to find them are usually different in each case.

-
Actually, writing it backwards is quite an artificial trick, okay for a slick proof but I don't think it's the natural way anyone would have derived it. It's more natural to observe that sum of first and last term = sum of second and penultimate term and so on, i.e., 1 + n = 2 + n-1 = 3 + n-2, etc., so there are n/2 terms each equal to n+1. This is less slick because you have to think a little about what happens when n is odd, but it's more natural – ShreevatsaR Jul 22 '11 at 17:09