1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by induction an expression

  1. Apr 28, 2012 #1
    I'm trying to prove by induction the expression:

    [itex]\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}[/itex]

    For the base case, n=2, S(2)=[itex]\frac{2(2-1)}{2}=1[/itex]

    For S(n+1)=[itex]\frac{(n+1)((n+1)-1)}{2}[/itex] I have:

    S(n+1) = [itex]\frac{n(n-1)}{2}[/itex] + (n+1) <--- Is this correct?

    I don't know what is the term for n+1. Any help?
     
    Last edited: Apr 28, 2012
  2. jcsd
  3. Apr 28, 2012 #2

    HallsofIvy

    User Avatar
    Science Advisor

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

    No one can tell you until you tell us what is being summed.
     
  4. Apr 28, 2012 #3
    I corrected in the first message now.
     
  5. Apr 28, 2012 #4
    I solved. Here's the solution. Can you check it if it's right?

    For n=2, I got
    0+1=[itex]\frac{2(2-1)}{2}[/itex]

    For n=3,
    0+1+2=[itex]\frac{3(3-1)}{2}[/itex]

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

    For n+1 I got
    0+1+2+3+...+n-1+n=[itex]\frac{(n+1)(n+1-1)}{2}=\frac{(n+1)(n)}{2}[/itex]

    For the LHS

    LHS=[itex]\frac{n(n-1)}{2}+n=\frac{n(n-1)+2n}{2}=\frac{n^2-n+2n}{2}=\frac{n^2+n}{2}[/itex]

    For the RHS
    RHS=[itex]\frac{(n+1)(n)}{2}=\frac{n^2+n}{2}[/itex]

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

    Is this solution correct?
     
  6. Apr 28, 2012 #5

    HallsofIvy

    User Avatar
    Science Advisor

    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
    [tex]\sum_{i= 1}^{n- 1} n- 1= \sum_{j= 0}^n j[/tex]
    where I have taken j= i- 1.

    If I really didn't want to do that, I might note that
    [tex]\sum_{i=1}^{n-1}= n\sum_{i= 1}^n 1- \sum_{i=1}^{n- 1}i[/tex]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook