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!

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
    Staff Emeritus
    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
    Staff Emeritus
    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]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by induction an expression
  1. Induction Proof (Replies: 7)

  2. Induction proof (Replies: 1)

  3. Proof By Induction (Replies: 2)

  4. Proof by induction (Replies: 1)

  5. Proof by Induction (Replies: 3)

Loading...