Results 1 to 8 of 8

Math Help - Anyone a pro at proof by mathematical induction?

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    14

    Anyone a pro at proof by mathematical induction?

    Can anyone help me prove (k(k-1)/2)^2 by mathematical induction
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor kalagota's Avatar
    Joined
    Oct 2007
    From
    Taguig City, Philippines
    Posts
    1,026
    Quote Originally Posted by hats_06 View Post
    Can anyone help me prove (k(k-1)/2)^2 by mathematical induction
    where is it equal to or what?

     \left( {\frac{k(k-1)}{2}} \right)^2 = ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, hats_06!

    Can anyone help me prove (k(k-1)/2)^2 by mathematical induction?
    Please state the original equation.

    What you're asking is: "Can anyone prove 36?"


    I recognize the expression.
    It may have come from: . 1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 \;=\;\left[\frac{k(k-1)}{2}\right]^2

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2007
    Posts
    14
    yes thats it thanks, would you be able to prove that (by mathematical induction)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,846
    Thanks
    321
    Awards
    1
    Quote Originally Posted by hats_06 View Post
    yes thats it thanks, would you be able to prove that (by mathematical induction)?
    You wish to prove
    \sum_{i = 1}^{k - 1}i^3 = \frac{k^2(k - 1)^2}{4}

    The base case is k = 2:
    \sum_{i = 1}^{1}i^3 = \frac{2^2(2 - 1)^2}{4} = 1 (check!)

    Now assume theorem is true for some value of k, say n. So we are assuming
    \sum_{i = 1}^{n - 1}i^3 = \frac{n^2(n - 1)^2}{4}

    Now we need to show that
    \sum_{i = 1}^{(n + 1) - 1}i^3 = \frac{(n + 1)^2((n + 1) - 1)^2}{4}

    or
    \sum_{i = 1}^{n}i^3 = \frac{(n + 1)^2n^2}{4}

    The LHS is:
    \sum_{i = 1}^{n}i^3 = \sum_{i = 1}^{n - 1} + n^3

    = \frac{n^2(n - 1)^2}{4} + n^3
    by assumption.

    = \frac{n^2(n - 1)^2}{4} + \frac{4n^3}{4}

    = \frac{n^2(n - 1)^2 + 4n^3}{4}

    = \frac{n^2(n^2 - 2n + 1) + 4n^3}{4}

    = \frac{n^4 - 2n^3 + n^2 + 4n^3}{4}

    = \frac{n^4 + 2n^3 + n^2}{4}

    = \frac{n^2(n^2 + 2n + 1)}{4}

    = \frac{n^2(n + 1)^2}{4}
    which is your RHS.

    Thus it is true for k = 2, so it true for k = 3, etc.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2007
    Posts
    14
    Thanks heaps for that!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,846
    Thanks
    321
    Awards
    1
    Quote Originally Posted by hats_06 View Post
    Thanks heaps for that!
    Induction proofs usually all follow the same pattern in that they use the assumption case (k = n) to simplify the LHS of the equation to make it easier to get it into the form on the RHS.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello again, hats_06!

    I must assume you know the routine for an inductive proof.


    Prove by induction: . 0^3 + 1^3 + 2^3 + 3^3 + \cdots + (n-1)^3 \;=\;\left[\frac{n(n-1)}{2}\right]^2
    Verify S(1)\!:\;\;0^3 \:=\:\left[\frac{1(0)}{2}\right]^2 \:=\:0 . . . True!


    Assume S(k) is true: . 0^3 + 1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 \:=\:\left[\frac{k(k-1)}{2}\right]^2


    Add k^3 to both sides:
    . . \underbrace{1^3 + 2^3 + 3^3 + \cdots + (k-1)^3 + k^3}_{\text{This is the left side of }S(k+1)} \;=\;\left[\frac{k(k-1)}{2}\right]^2 +k^3


    The right side is: . \frac{k^2(k-1)^2}{4} + k^3

    Factor: . \frac{k^2}{4}\left[(k-1)^2 + 4k\right] \;=\;\frac{k^2}{4}\left[k^2-2k+1+4k\right] \;=\;\frac{k^2}{4}\left(k^2 + 2k + 1\right]

    . . . = \;\frac{k^2}{4}(k+1)^2 \;=\;\underbrace{\left[\frac{k(k+1)}{2}\right]^2}_{\text{Right side of }S(k+1)}


    We have proved S(k+1)\!:\;\;0^3 + 1^3 + 2^3 + \cdots + k^3 \;=\;\left[\frac{k(k+1)}{2}\right]^2
    . . The inductive proof is complete.



    Ha! . . . Dan beat me to it (again) . . .
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 24th 2011, 02:33 PM
  2. Proof by mathematical induction.
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: June 23rd 2011, 09:12 PM
  3. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 5th 2010, 11:24 AM
  4. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2010, 05:36 PM
  5. proof and mathematical induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 11th 2007, 11:16 AM

Search Tags


/mathhelpforum @mathhelpforum