Results 1 to 12 of 12

Math Help - Induction Question!!!

  1. #1
    Newbie
    Joined
    Apr 2005
    Posts
    21

    Induction Question!!!

    can anyone help with this induction problem:

    n = n (n+1)

    i'm having trouble proving true for n = k+1

    i need to prove that (k+1) = (k+1) (k+2) (i hope this is right)

    by assumption the LHS should be k (k+1) (k+1) is it not?

    can someone help me as to solving this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2007
    From
    Cambridge, UK
    Posts
    41
    This identity should be very hard to prove - because it's not true!

    Counterexample: consider n = 10.

    n^3 = 1000;
    \frac{1}{4} n^2 (n+1)^2 = \frac{10^2 \cdot 11^2}{4} = 3025.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,079
    Thanks
    375
    Awards
    1
    I believe the expression should be:
    \sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+ 1)^2

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,079
    Thanks
    375
    Awards
    1
    Quote Originally Posted by topsquark View Post
    I believe the expression should be:
    \sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+ 1)^2

    -Dan
    Let n = 1:
    Then
    \sum_{k = 1}^1k^3 = 1
    \frac{1}{4}1^2(1 + 1)^2 = 1 (Check!)

    So assume this is true for some value of n. We need to show it is true for n + 1. That is, assume
    \sum_{k = 1}^nk^3 = \frac{1}{4}n^2(n+ 1)^2

    We need to show this for
    \sum_{k = 1}^{n+ 1}k^3 = \frac{1}{4}(n+ 1)^2(n+ 2)^2

    Well,
    \sum_{k = 1}^{n+ 1}k^3 = \sum_{k = 1}^nk^3 + (n + 1)^3

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

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

    = \frac{1}{4}n^2([n^2 + 2n + 1] + 2n + 3) + <br />
\frac{1}{4}(2n + 1)(n^2 + 4n + 4)

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

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

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

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

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

    = \sum_{k = 1}^nk^3 + (n + 1)^3

    as required.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    What you mean is prove:

    <br />
\sum_{r=1}^n r^3 = \frac{n^2(n+1)^2}{4}<br />

    RonL
    If this is true for n=k, then:

    <br />
\sum_{r=1}^{k+1} r^3 = \sum_{r=1}^{k} r^3+ (k+1)^3=\frac{k^2(k+1)^2}{4}+(k+1)^3<br />

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

    Which completes the inductive step and the rest is plain sailing.

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,811
    Thanks
    701
    Hello, Chuck!

    Prove by induction: . \sum^n_{i=1} i^3 \:=\:\frac{n^2(n+1)^2}{4}
    You've already verified S(1), right?

    We assume S(k) is true: . 1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}

    Add (k+1)^3 to both sides:
    . . \underbrace{1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3} \;=\;\frac{k^2(x+1)^2}{4} + (k+1)^3
    . . The left side is the left side of S(k+1).


    Factor the right side: . (k+1)^2\left[\frac{k^2}{4} + (k+1)\right] \;=\;(k+1)^2\left[\frac{k^2+4k+4}{4}\right] \;=\;\frac{(k+1)^2(k+2)^2}{4}
    . . This is the right side of S(k+1).


    Therefore, we have: . 1^3+ 2^3 + 3^3 + \cdots + (k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}
    . . and the inductive proof is complete.

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,079
    Thanks
    375
    Awards
    1
    Quote Originally Posted by Soroban View Post
    Hello, Chuck!

    You've already verified S(1), right?

    We assume S(k) is true: . 1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}

    Add (k+1)^3 to both sides:
    . . \underbrace{1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3} \;=\;\frac{k^2(x+1)^2}{4} + (k+1)^3
    . . The left side is the left side of S(k+1).


    Factor the right side: . (k+1)^2\left[\frac{k^2}{4} + (k+1)\right] \;=\;(k+1)^2\left[\frac{k^2+4k+4}{4}\right] \;=\;\frac{(k+1)^2(k+2)^2}{4}
    . . This is the right side of S(k+1).


    Therefore, we have: . 1^3+ 2^3 + 3^3 + \cdots + (k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}
    . . and the inductive proof is complete.

    Aw shucks! That was the easy way to do it! (I figured there had to be one...)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    ActionBallMan
    Guest

    Smile Hi im new here :)

    I was going to start a new thread but I decided to tagg along this one. Okay I have two problems. Please explain this clearly. Im really having a hard time understanding this stuff.


    Prove by induction that for any x, if x 1, then 3n 1 + 2n.
    Step 1:For x =, P() = [(3 1) = 1 + 2].The base case is (Type T/F.).Step 2:For k suppose that 3k 1 + 2k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 + 2(k + 1)This becomes3k + (1 + 2) + 2We conclude the statement is(Type T/F.)because the left side increases more than the right.

    Prove by induction that for any x, if x 1, then 5n 1 + 4n .
    Step 1:For x = 1, P(1) = [(5 1) = 1 +].The base case is (Type T/F.).Step 2:For k suppose that 5k 1 + 4k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 +(k + 1)This becomes5k + (1 + 4) + 4We conclude the statement is (Type T/F.)because the left side increases more than the right.

    Thank You!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ActionBallMan View Post
    I was going to start a new thread but I decided to tagg along this one. Okay I have two problems. Please explain this clearly. Im really having a hard time understanding this stuff.


    Prove by induction that for any x, if x 1, then 3n 1 + 2n.
    Step 1:For x =, P() = [(3 1) = 1 + 2].The base case is (Type T/F.).Step 2:For k suppose that 3k 1 + 2k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 + 2(k + 1)This becomes3k + (1 + 2) + 2We conclude the statement is(Type T/F.)because the left side increases more than the right.

    Prove by induction that for any x, if x 1, then 5n 1 + 4n .
    Step 1:For x = 1, P(1) = [(5 1) = 1 +].The base case is (Type T/F.).Step 2:For k suppose that 5k 1 + 4k is(Type T/F.)Step 3:Add in the termNow the expression is(k + 1) 1 +(k + 1)This becomes5k + (1 + 4) + 4We conclude the statement is (Type T/F.)because the left side increases more than the right.

    Thank You!
    are these your proofs, or were they given to you and you're trying to understand them? there seems to be some stuff missing. do you understand the general method of proving things by induction?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ActionBallMan View Post
    Prove by induction that for any x, if x 1, then 3x 1 + 2x.
    ok, so first of all, you had different variables, everything must be in one variable. you cant make a statement about x and then prove something about n when we don't know anything about n. i changed everything to x. Here's how i would do them

    Let P(x): "If x \geq 1, then 3x \geq 1 + 2x for all integers x"

    We have for the base case:

    P(1): 3(1) = 3 \geq 1 + 2(1) = 3, so P(1) is true

    Assume P(k) is true for some k \geq 1. We show that P(k + 1) is true

    Since P(k) is true, we have:

    3k \geq 1 + 2k

    It follows that:

    3 k + 3 \geq 1 + 2k + 2, since we add 3 to the left and 2 to the right

    But we can factor this so that:

    3(k + 1) \geq 1 + 2(k + 1) which is P(k + 1)

    Thus the inductive proof is complete and P(x) holds true for all integers x \geq 1


    Prove by induction that for any n, if n 1, then 5n 1 + 4n .
    This one is pretty much the same as the last.


    Let P(n): "If n \geq 1, then 5n \geq 1 + 4n for all integers n"

    So P(1): 5(1) = 5 \geq 1 + 4(1) = 5. So P(1) is true

    Assume P(k) true for some k \geq 1, we show that P(k + 1) is true

    Since P(k) is true, we have:

    5k \geq 1 + 4k

    It follows that:

    5k + 5 \geq 1 + 4k + 4

    Factoring we get:

    5(k + 1) \geq 1 + 4(k + 1), which is P(k + 1)

    Thus the inductive proof is complete, and P(n) holds for all integers n \geq 1
    Last edited by Jhevon; June 15th 2007 at 09:55 PM. Reason: forgot to specify the set we were talking about. Thanks CaptainBlack
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jhevon View Post
    ok, so first of all, you had different variables, everything must be in one variable. you cant make a statement about x and then prove something about n when we don't know anything about n. i changed everything to x. Here's how i would do them

    Let P(x): "If x \geq 1, then 3n \geq 1 + 2n"

    We have for the base case:

    P(1): 3(1) = 3 \geq 1 + 2(1) = 3, so P(1) is true

    Assume P(k) is true for some k \geq 1. We show that P(k + 1) is true

    Since P(k) is true, we have:

    3k \geq 1 + 2k

    It follows that:

    3 k + 3 \geq 1 + 2k + 2, since we add 3 to the left and 2 to the right

    But we can factor this so that:

    3(k + 1) \geq 1 + 2(k + 1) which is P(k + 1)

    Thus the inductive proof is complete and P(x) holds true for all x \geq 1


    This one is pretty much the same as the last.


    Let P(n): "If n \geq 1, then 5n \geq 1 + 4n"

    So P(1): 5(1) = 5 \geq 1 + 4(1) = 5. So P(1) is true

    Assume P(k) true for some k \geq 1, we show that P(k + 1) is true

    Since P(k) is true, we have:

    5k \geq 1 + 4k

    It follows that:

    5k + 5 \geq 1 + 4k + 4

    Factoring we get:

    5(k + 1) \geq 1 + 4(k + 1), which is P(k + 1)

    Thus the inductive proof is complete, and P(n) holds for all n \geq 1

    There is a flaw in the statement of the problem, and what you have proven
    (lets forget the mixtue of [tex]x[tex]'s and n'n for the moment)

    Induction in the form used will only prove these statments for all
    integers n \ge 1, or whatever, not for all n in some unspecified set.

    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by CaptainBlack View Post
    There is a flaw in the statement of the problem, and what you have proven
    (lets forget the mixtue of [tex]x[tex]'s and n'n for the moment)

    Induction in the form used will only prove these statments for all
    integers n \ge 1, or whatever, not for all n in some unspecified set.

    RonL
    yes, you are right. i was thinking about intergers though, just neglected to say it. I changed it
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 7th 2009, 12:44 PM
  2. Induction question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 2nd 2009, 01:32 AM
  3. induction question..
    Posted in the Calculus Forum
    Replies: 5
    Last Post: January 6th 2009, 06:23 AM
  4. Question on induction
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: July 18th 2008, 08:49 PM
  5. induction question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 16th 2007, 08:14 AM

Search Tags


/mathhelpforum @mathhelpforum