Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Proof for formula for sum of sequence 1+2+3+…+n?

Can you explain this please $$T(n) = (n-1)+(n-2)+…1= \frac{(n-1)n}{2}$$

I am really bad at maths but need to understand this for software engineering.

share|improve this question

marked as duplicate by Asaf Karagila, Quixotic, Byron Schmuland, Willie Wong Nov 10 '11 at 15:36

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.

2  
What is it you are trying to understand? –  Arturo Magidin Nov 10 '11 at 14:28
    
just to explain this, what is the answer, how did you get it etc, what is this used for. –  java Nov 10 '11 at 14:30
    
See this. –  J. M. Nov 10 '11 at 14:31
2  
@java: The answer to what? This is an equation, not a question. –  Arturo Magidin Nov 10 '11 at 14:44

5 Answers 5

For example, if we wish to add the numbers

$$ 1+2+3+4+5+6 $$

you can pair them as such

$$ (1+6)+(2+5)+(3+4)=7+7+7=21. $$

But, here $n=7$ and there are $\frac{n-1}{2}=3$ pairs of $n=7$. Thus we have that the sum is $\frac{n-1}{2}\cdot n=3\cdot 7=21$. In general, you can pair the sum

$$ 1+2+3+\cdots +(n-2)+(n-1) $$

as pairs $(n-1+1), (n-2+2), (n-3+3), \ldots$ and so forth. This will give you $\frac{n-1}{2}$ pairs of $n$ if $n-1$ is even. If $n-1$ is odd, leave off $n-1$ and do it for $1+\cdots +(n-2)$ and add on $n-1$ to obtain the same formula.

share|improve this answer

It says that the following two programs give the same output:

int mySum( int integer)
{
if( integer == 1)
     return 1;
else
       {
       return(integer+(mySum(integer-1));
       }
}

and

int mySum2( int integer)
{
   return(integer*(integer+1)/2);
}
share|improve this answer
    
For obvious reasons,if(1==integer) is a good practice :) –  Quixotic Nov 10 '11 at 15:28
    
@MaX I actually think that's terrible practice. What you gain (slightly lower probability of making a mistake) is small, what you lose (readability of your program) is large. Any modern IDE will flag up if you write i = 1 instead of i == 1 inside a conditional anyway. –  Chris Taylor Nov 10 '11 at 15:33

Edited to correct the attribution to Gauss as noted by @KaratugOzanBircan

By Gauss:

$\begin{array}{ccccc}T(n)&=&(n-1)&+&(n-2)&+&\cdots&+&2&+1\\T(n)&=&1&+&2&+&\cdots&+&(n-2)&+&(n-1)\end{array}$


$2T(n)=n+n+\cdots+n$ ($n-1$ times)=$n.(n-1)$

Hence $T(n)=\frac{n(n-1)}{2}$

share|improve this answer
    
The Gauss'story is apocryphal... –  Quixotic Nov 10 '11 at 15:03
    
@MaX: Like many things I don't bother about verification :) –  Tapu Nov 10 '11 at 15:09
    
Sure,but may be then you won't then like to give credit in the beginning :)Btw I was just stating what I read somewhere in here before no offence meant :) –  Quixotic Nov 10 '11 at 15:21
    
In case if you ever want to here is the link –  Quixotic Nov 10 '11 at 15:26
    
Thank you MaX, it indeed is a nice article. I knew about Newton's (apple) and Archimedes (bathtub, Kill me but don't kill my geometry) story, but has no idea about Gauss's. –  Tapu Nov 10 '11 at 15:46

Here is a story that is attributed to Gauss.

His teacher asked him to sum $1+2+3+...+99$. Then Gauss summed this terms with the same terms but with the reverse order, i.e., $(1+99)+(2+98)+(3+97)+...+(98+2)+(99+1).$ The trick here is that the sum of each term in paranthesis is 100 and we have 99 terms. But he summed the terms twice, so he needed to divide the sum by 2. Hence the sum is $(99\times 100) /2.$

So if we generalize this, we get the formula.

share|improve this answer

Say, $$K = (n-1) + (n-2) + \cdots + 2 + 1$$

Writting it backwards: $$K = 1 + 2 + \cdots + (n-2)+(n-1)$$

Lets add the two equations, which gives, $$2k = n + n + \cdots + n$$ Note that each term is $n$ and there are exactly $(n-1$) terms, so$$2k = n + n + \cdots + n = n(n-1)$$

Dividing by $2$: $$K= (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n-1)}{2}$$

For more of intutive proofs of this identity see here.

share|improve this answer

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