Results 1 to 2 of 2

Math Help - Induction

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,902
    Thanks
    329
    Awards
    1

    Induction

    This post has been moved to a more appropriate place.
    Quote Originally Posted by >_<SHY_GUY>_< View Post
    Hi, im taking an algebra II course that teaches both Algebra A and B in one semester. one thing i don't understand that we have been going through is proof by induction. i dont get the steps, i dont understand it. here are some equations that we reviewed in which i didn't understand:

    1. 2+4+6+8+...+2n= n(n+1)

    2. 1+5+9+13+...+(4n-3)= n(2n-1)

    3. 3+8+13+18+...+(5n-2)= n/2 (5n+1)

    4. 1+2^2+2^3+...+2^n-1= 2^n-1 [^ is used to express in exponents since i dont know how to put it here]

    5. 1^3+2^3+3^3+4^3+...+n^3= n^2 (n+1)^2/ 4

    i was wondering if you can help me because after the teacher doing these, i could not understand how she got (k+1) in some of the equations and how to use it. i am in dieing need of help and i would greatly appreciate it if you can help me
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,715
    Thanks
    633
    Hello, Shy Guy!

    Do you understand the procedure for an inductive proof?

    We are given a statement S(n) which is allegedly true for all natural numbers n.

    . . (1) Verify that statement S(1) is true.

    . . (2) Assume that statement S(k) is true.

    . . (3) Prove that statement S(k+1) is true.


    I'll walk through a couple of these for you . . .



    1)\;\;2 + 4 + 6 + 8 + \cdots + 2n \:=\:n(n+1)
    (1) Verify S(1) . . . Substitute n=1.

    We have: . 2 \:=\:1(1+1)\quad\Rightarrow\quad 2 \:=\:2\quad \hdots\quad \text{true!}


    (2) Assume that: . 2 + 4 + 6 + 8 + \cdots + 2k \;=\;k(k+1)


    (3) Prove that S(k+1) is true.
    The statement looks like this: . {\color{blue}2 + 4 + 6 + \cdots  + 2k +2(k+1) \;=\;(k+1)(k+2)}
    . . [This is what we wish to prove.]

    Start with S(k)\!:\;\;2 + 4 + 6 + \cdots + 2k \;=\;k(k+1)

    Add 2(k+1) to both sides: . 2 + 4 + 6 + \cdots + 2k + 2(k+1) \;=\;k(k+1) + 2(k+1)

    . . The right side is: . k+1)(k+2)" alt="k(k+1) + 2(k+1) \:=\:k^2 + k + 2k + 2 \:=\:k^2 + 3k + 2 \:=\k+1)(k+2)" />


    The equation becomes: . 2 + 4 + 6 + \cdots + 2k + 2(k+1) \;=\;(k+1)(k+2)

    This is S(k+1) . . . The inductive proof is compete!

    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


    5)\;\;1^3 + 2^3 + 3^3 + \cdots + n^3 \;=\;\frac{n^2(n+1)^2}{4}

    (1) Verify S(1) . . . Substitute n=1.

    We have: . 1^3\:=\:\frac{1^2(1+1)^2}{4}\quad\Rightarrow\quad 1 \:=\:1\quad \hdots\quad \text{true!}


    (2) Assume that: . 1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}


    (3) Prove that S(k+1) is true.
    The statement looks like this: . {\color{blue}1^3 + 2^3 + 3^3 + \cdots  + k^3 +(k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}}
    . . [This is what we wish to prove.]

    Start with S(k)\!:\;\;1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}

    Add (k+1)^3 to both sides: . 1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3 \;=\;\frac{k^2(k+1)^2}{4} + (k+1)^3

    . . The right side is: . \frac{k^2(k+1)^2}{4} + (k+1)^3 \;=\;\frac{(k+1)^2}{4}\,[k^2 + 4(k+1)]

    . . . . =\;\frac{(k+1)^2}{4}[k^2+4k+4] \;=\;\frac{(k+1)^2(k+2)^2}{4}


    The equation becomes: . 1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}

    This is S(k+1) . . . The inductive proof is compete!

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum