Results 1 to 2 of 2

Math Help - Induction Proof

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    401

    Induction Proof

    Here is the problem:

    "Let S_n stand for the sum of all the products of the integers, taken two at a time, from 1 to n. For example, S_4 means:

    S_4 = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4

    Prove that S_n is given explicitly by:

    S_n = [n*(n^2-1)*(3*n+2)]/24".

    So, I was thinking this was the perfect candidate for an induction proof. I thought it would be best to derive the formula first:

    Derive formula S_(n+1) = S_n + 1(n+1) + 2(n+1) + ... + n(n+1)
    = S_n + n(n + 1)^2 / 2

    Now what; base case of course works out. How do I work toward the induction assumption.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by AfterShock
    Here is the problem:

    "Let S_n stand for the sum of all the products of the integers, taken two at a time, from 1 to n. For example, S_4 means:

    S_4 = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4

    Prove that S_n is given explicitly by:

    S_n = [n*(n^2-1)*(3*n+2)]/24".

    So, I was thinking this was the perfect candidate for an induction proof. I thought it would be best to derive the formula first:

    Derive formula S_(n+1) = S_n + 1(n+1) + 2(n+1) + ... + n(n+1)
    = S_n + n(n + 1)^2 / 2

    Now what; base case of course works out. How do I work toward the induction assumption.
    Suppose that for some k \ge 2 that

    S_k = \frac{k(k^2-1)(3k+2)}{24}

    Now you need to show that:

    S_{k+1}=\frac{(k+1)((k^2+2k)(3k+5)}{24}\ \ \ \dots (1).

    But you already know that:

     S_{k+1}=S_k + \frac{k(k + 1)^2}{ 2}=  \frac{k(k^2-1)(3k+2)}{24} + \frac{k(k + 1)^2}{ 2}\ \ \ \dots (2)

    So you need to show that the RHS of (1) is equal to the
    RHS of (2). Then you will have shown that if the formula for
    S_k is true for some k \ge 2 it is true for k+1. Which is what
    you need with the base case to complete the proof.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum