1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction Problem

  1. Jul 11, 2007 #1
    I have recently been introduced to mathematical induction in my discrete mathematics course. This is the first time I’ve ever seen induction, and so of course I was very confused. I am still confused, but not as much as before. I’m doing problems out of the book for practice, but I’m not sure if this is correct so far. I’m also not sure how to proceed with the inductive step. If someone could critique my work and guide me through the rest of the problem that would be great. On a side note, do you guys think that I might be in over my head with a discrete mathematics course? I’m fresh out of high school, and the last math class I took was pre-calculus. I wanted to get a head start on college, but now that I’m reaching induction, recursion, etc… I feel like I cannot keep up with the class. A lot of the other people in my class seem to be way more advanced as far as understand computer science and math, and so I begin to wonder whether or not I made a mistake. Thanks guys.

    Let P(n) be the statement that 1^2 + 2^2 + … + n^2 = n(n+1)(2n+1)/6

    for the positive integer n.

    a)What is the statement P(1)?

    P(1) = 1(1+1) (2(1)+1)/6 = 1(2)(3)/6 = 6/6 = 1


    b)Show that P(1) is true, completing the basis step of the proof

    1^2 = 1, and since the above equation results in 1. Therefore, P(1) is true.


    c)What is the inductive hypothesis?

    (A) : “1^2 + 2^2 + … + k^2 = k(k+1)(2k+1)/6” where k is any positive integer.


    (B): “1^2 + 2^2 +…+ k^2 + (k+1)^2 = (k+1)(k+1) (2 (k+1) +1)/6”

    Assuming A, we will prove B.


    d)What do you need to prove in the inductive step?

    Assuming that A is true, you need to prove B.


    e) Complete the inductive step
     
    Last edited: Jul 11, 2007
  2. jcsd
  3. Jul 11, 2007 #2

    berkeman

    User Avatar

    Staff: Mentor

    I think there is a small omission in your B step. Each "k" in the statement A needs to be replaced with "k+1" in the inductive B step. On the right hand side, you have (k+1)(k+1)(..... instead of (k+1)(k+1+1)(.....


    BTW, I'm going to move this question to a more math-oriented forum here in the Homework Help forums.
     
    Last edited: Jul 11, 2007
  4. Jul 11, 2007 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Once you followed berkeman's advice then the difference of the left hand sides of A and B is (k+1)^2. What is the difference of the right hand sides? What do you conclude?
     
  5. Jul 11, 2007 #4
    is the difference: 3k^3 + k^2 + 7k + 3 ?
    I just took both right hand sides, tried to simplify and then subtract.
    Whether or not I'm right, I still don't see how to prove it.
     
  6. Jul 11, 2007 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You did the algebra wrong. How could you get a k^3 term? Expand both products.
     
  7. Jul 11, 2007 #6

    berkeman

    User Avatar

    Staff: Mentor

    Well said, Dick. Chromium, did you understand what Dick is illustrating here for you?
     
  8. Jul 11, 2007 #7
    To be honest, no. I understood the difference between the left sides, but not the right side.
     
  9. Jul 11, 2007 #8

    berkeman

    User Avatar

    Staff: Mentor

    Okay, to help clear it up, please re-write the A and B lines (making the correction to the B line that I pointed out) for us. Now, re-write the B line isolating the term that Dick mentioned on the lefthand side. Now the LHS of the B line looks like the A line's LHS, but with that extra term, right?

    Now look at the RHS of the B line. Re-write it as the RHS of the A line, and isolate whatever terms you need to pull out to make the rest match the A line. What did you end up pulling out?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Induction Problem
  1. Induction Problem (Replies: 8)

  2. Induction Problem (Replies: 3)

  3. A problem on Induction (Replies: 29)

Loading...