Results 1 to 8 of 8

Math Help - Mathematical Induction help

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    45

    Mathematical Induction help

    Hi all, Im new to the forum and I am having difficulties understanding Inductions.

    I have these 2 examples from the textbook and they give me answers but I was wondering if anyone can help me through it. I keep staring at it and it just doesn't sink in.

    1st problem:
    Prove that the sum of the first N odd positive integers = n^2

    I get the first step prove that P(1) = true which is sum of the first odd integer which is 1 and 1^2 = 1.

    The textbook puts 1+3+5+...+(2k-1)=k^2
    I know 2k-1 ='s an odd integer but this is what confuses me

    the textbook has 1+3+5....+(2k-1)+(2k+1) = (k+1)^2
    then..
    has 1+3+5....+(2k-1)+(2k+1) = [1+3+...(2k-1)] + (2k+1)
    =k^2 + (2k+1) ---where did k^2 come from?
    =k^2 + 2k + 1
    =(k+1)^2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by ff4930 View Post
    Hi all, Im new to the forum and I am having difficulties understanding Inductions.

    I have these 2 examples from the textbook and they give me answers but I was wondering if anyone can help me through it. I keep staring at it and it just doesn't sink in.

    1st problem:
    Prove that the sum of the first N odd positive integers = n^2

    I get the first step prove that P(1) = true which is sum of the first odd integer which is 1 and 1^2 = 1.

    The textbook puts 1+3+5+...+(2k-1)=k^2
    I know 2k-1 ='s an odd integer but this is what confuses me

    the textbook has 1+3+5....+(2k-1)+(2k+1) = (k+1)^2
    then..
    has 1+3+5....+(2k-1)+(2k+1) = [1+3+...(2k-1)] + (2k+1)
    =k^2 + (2k+1) ---where did k^2 come from?
    =k^2 + 2k + 1
    =(k+1)^2
    Typically in a mathematical induction problem you prove the statement for some specific value of k, then use the theorem itself to simplify your problem.

    Specifically in your case we know that the theorem is true for k = 1.

    Let me change your variables a bit. (This may make this more transparent, or it may confuse you. I hope the former!) Assume the theorem is true for some k = n. Then
    1 + 3 + ~ ... ~ + (2n - 1) = n^2

    We need to show that the theorem is true for the next value of k, n + 1. That is, we need to show that:
    1 + 3 + ~ ... ~ + (2n - 1) + (2n + 1) = (n + 1)^2

    Break down the sum on the LHS:
    (1 + 3 + ~ ... ~ + (2n - 1)) + (2n + 1) = (n + 1)^2

    The sum in parenthesis is just n^2, according to our assumption. So we have:
    n^2 + (2n + 1) = (n + 1)^2
    which is an identity, so the theorem is true for k = 1, thus k = 2, 3, 4, ...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2007
    Posts
    45
    Thanks for the detailed explanation but I dont get this part

    We need to show that the theorem is true for the next value of k, n + 1. That is, we need to show that:
    why is it 2n+1?
    wouldn't next value be another odd integer which is (2n-1), and since is k+1 wouldn't it be (2n-1)+1? sorry if Im not seeing it right away.

    Ok, is this right?
    because they give us the formula for the next odd integer is 2 times(n-1)
    so to find n+1 it is 2 times(n+1)?
    Last edited by ff4930; August 4th 2007 at 12:20 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by ff4930 View Post
    Thanks for the detailed explanation but I dont get this part

    why is it 2n+1?
    wouldn't next value be another odd integer which is (2n-1), and since is k+1 wouldn't it be (2n-1)+1? sorry if Im not seeing it right away.

    Ok, is this right?
    because they give us the formula for the next odd integer is 2 times(n-1)
    so to find n+1 it is 2 times(n+1)?
    The formula for the "k"th odd integer is 2k - 1. So the next one will be:
    2(k + 1) - 1 = 2k + 2 - 1 = 2k + 1

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2007
    Posts
    45
    Thank you for your help.

    Ive tried applying what Ive learned from that to the 2nd example and if you can help clarify it because Im a little stuck.

    prove n < 2^n
    for all positive integers n

    always have to prove the base step which is easy P(1) = 1 < 2^1 = 2

    Then I have to prove that it is also correct for k+1 integers
    which is to prove K + 1 < 2 ^k+1

    Here is where Im stuck, the textbook says add 1 to both sides of k < 2^k, noting that 1 <= 2^k
    which is k+1 < 2^k +1 <= 2^k + 2^k = 2^k+1

    I just dont understand where the 2^k + 2^k came from.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by ff4930 View Post
    Thank you for your help.

    Ive tried applying what Ive learned from that to the 2nd example and if you can help clarify it because Im a little stuck.

    prove n < 2^n
    for all positive integers n

    always have to prove the base step which is easy P(1) = 1 < 2^1 = 2

    Then I have to prove that it is also correct for k+1 integers
    which is to prove K + 1 < 2 ^k+1

    Here is where Im stuck, the textbook says add 1 to both sides of k < 2^k, noting that 1 <= 2^k
    which is k+1 < 2^k +1 <= 2^k + 2^k = 2^k+1

    I just dont understand where the 2^k + 2^k came from.
    One thing that is definitely confusing you is your notation. PLEASE USE PARENTHESIS!!!
    You need to show that if
    n < 2^n

    That
    n + 1 < 2^{n + 1}
    (If you can't use the fancy LaTeX, write this as "n + 1 < 2^(n + 1)")

    So let's take the hint. Let's look at
    n < 2^n
    and add 1 to both sides:

    n + 1 < 2^n + 1 <-- "2^n + 1" is NOT "2^(n + 1)" This was an error in your work, I think.

    Now, note that
    2^{n + 1} = 2^n \cdot 2 = 2^n + 2^n

    and because 1 \leq n we also know that 1 < 2 \leq 2^n

    So
    n + 1 < 2^n + 1 < 2^n + 2^n = 2^{n + 1}

    Thus
    n + 1 < 2^{n + 1}

    (Note: There may be an easier way to do this. This method was the first one that came to me after looking at the hint.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Aug 2007
    Posts
    45
    Thank You very much for taking time out to explain it.
    My problem is grasping the information. Im going to die when the exam comes if Im having so much trouble with examples. Hopefully after some practice problems Ill be allright. Thanks again.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by ff4930 View Post
    Thank You very much for taking time out to explain it.
    My problem is grasping the information. Im going to die when the exam comes if Im having so much trouble with examples. Hopefully after some practice problems Ill be allright. Thanks again.
    Worry makes its own problems. Just find as many problems to work as you can and you'll get it down. Practice, practice, practice...

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 31st 2010, 03:31 PM
  2. Mathematical induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 30th 2010, 05:54 AM
  3. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  4. mathematical induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2009, 05:29 PM
  5. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 18th 2009, 08:35 AM

Search Tags


/mathhelpforum @mathhelpforum