Induction Problem

1. Jul 11, 2007

Chromium

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. Jul 11, 2007

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
3. Jul 11, 2007

Dick

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?

4. Jul 11, 2007

Chromium

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.

5. Jul 11, 2007

Dick

You did the algebra wrong. How could you get a k^3 term? Expand both products.

6. Jul 11, 2007

Staff: Mentor

Well said, Dick. Chromium, did you understand what Dick is illustrating here for you?

7. Jul 11, 2007

Chromium

To be honest, no. I understood the difference between the left sides, but not the right side.

8. Jul 11, 2007

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?