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

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.

-

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

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. –  Ｊ. Ｍ. Nov 10 '11 at 14:31
@java: The answer to what? This is an equation, not a question. –  Arturo Magidin Nov 10 '11 at 14:44

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.

-

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);
}

-
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}$

-
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.

-

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.

-