3
$\begingroup$

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.

  • 2
    What is it you are trying to understand?2011-11-10
  • 0
    just to explain this, what is the answer, how did you get it etc, what is this used for.2011-11-10
  • 0
    See [this](http://math.stackexchange.com/questions/60578).2011-11-10
  • 2
    @java: The answer to what? This is an equation, not a question.2011-11-10

5 Answers 5

3

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.

2

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);
}
  • 0
    For obvious reasons,`if(1==integer)` is a good practice :)2011-11-10
  • 0
    @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.2011-11-10
2

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.

2

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

  • 0
    The Gauss'story is apocryphal...2011-11-10
  • 0
    @MaX: Like many things I don't bother about verification :)2011-11-10
  • 0
    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 :)2011-11-10
  • 0
    In case if you ever want to here is the [link](http://www.americanscientist.org/issues/id.3483,y.0,no.,content.true,page.1,css.print/issue.aspx)2011-11-10
  • 0
    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.2011-11-10
  • 0
    Glad to help :)2011-11-10
0

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.