Results 1 to 2 of 2

Thread: Induction

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,129
    Thanks
    722
    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
    12,028
    Thanks
    848
    Hello, Shy Guy!

    Do you understand the procedure for an inductive proof?

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

    . . (1) Verify that statement $\displaystyle S(1)$ is true.

    . . (2) Assume that statement $\displaystyle S(k)$ is true.

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


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



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

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


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


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

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

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

    . . The right side is: .$\displaystyle k(k+1) + 2(k+1) \:=\:k^2 + k + 2k + 2 \:=\:k^2 + 3k + 2 \:=\k+1)(k+2)$


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

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

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


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

    (1) Verify $\displaystyle S(1)$ . . . Substitute $\displaystyle n=1.$

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


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


    (3) Prove that $\displaystyle S(k+1)$ is true.
    The statement looks like this: .$\displaystyle {\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 $\displaystyle S(k)\!:\;\;1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}$

    Add $\displaystyle (k+1)^3$ to both sides: .$\displaystyle 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: .$\displaystyle \frac{k^2(k+1)^2}{4} + (k+1)^3 \;=\;\frac{(k+1)^2}{4}\,[k^2 + 4(k+1)] $

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


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

    This is $\displaystyle 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: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Apr 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum