# Proof by induction an expression

1. Apr 28, 2012

### xeon123

I'm trying to prove by induction the expression:

$\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$

For the base case, n=2, S(2)=$\frac{2(2-1)}{2}=1$

For S(n+1)=$\frac{(n+1)((n+1)-1)}{2}$ I have:

S(n+1) = $\frac{n(n-1)}{2}$ + (n+1) <--- Is this correct?

I don't know what is the term for n+1. Any help?

Last edited: Apr 28, 2012
2. Apr 28, 2012

### HallsofIvy

Staff Emeritus
There appears to be something missing here! What is being summed?

No one can tell you until you tell us what is being summed.

3. Apr 28, 2012

### xeon123

I corrected in the first message now.

4. Apr 28, 2012

### xeon123

I solved. Here's the solution. Can you check it if it's right?

For n=2, I got
0+1=$\frac{2(2-1)}{2}$

For n=3,
0+1+2=$\frac{3(3-1)}{2}$

So, for n, I got
0+1+2+3+...+n-1=$\frac{n(n-1)}{2}$

For n+1 I got
0+1+2+3+...+n-1+n=$\frac{(n+1)(n+1-1)}{2}=\frac{(n+1)(n)}{2}$

For the LHS

LHS=$\frac{n(n-1)}{2}+n=\frac{n(n-1)+2n}{2}=\frac{n^2-n+2n}{2}=\frac{n^2+n}{2}$

For the RHS
RHS=$\frac{(n+1)(n)}{2}=\frac{n^2+n}{2}$

So, the LHS = RHS, proofing that $\frac{n(n-1)}{2}$ is correct for any n.

Is this solution correct?

5. Apr 28, 2012

### HallsofIvy

Staff Emeritus
What you have written is basically a "proof by induction" and, yes, it is correct.

Actually, the first thing I would do is write that as
$$\sum_{i= 1}^{n- 1} n- 1= \sum_{j= 0}^n j$$
where I have taken j= i- 1.

If I really didn't want to do that, I might note that
$$\sum_{i=1}^{n-1}= n\sum_{i= 1}^n 1- \sum_{i=1}^{n- 1}i$$

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook