# Mathematical Induction problem

1. Sep 29, 2005

### waterchan

I've been working on this problem for the past two and a half hours. The problem is: Prove by induction that n^3 + 2n is divisible by 3 for non-negative integer values of n.

No matter how I try, I cannot manipulate the expression of the inductive step so that it is divisible by 3.

I have done the base step and assumed that P(k): k^3 + 2k is divisible by 3. Now I need to show that this implies that P(k+1): (k+1)^3 + 2(k+1) is divisible by 3. I have tried manipulating P(k+1) in probably every possible way. The closest I have got to solving the problem, is getting part of the expression to be k^3 + 2k (which is divisible by 3 by assumption) and a constant 3.

(k+1)^3 + 2(k+1)

= k^3 + 2k^2 + 2k + 1 + 2k + 2

= k^3 + 2k^2 + 4k + 3

I also tried P(k+1) - P(k) and see if that would give an expression that is factorizable by 3. (Since the difference of two integers a and b is divisible by x, if and only if a and b are divisible by x.)

P(k+1) - P(k)

= [(k+1)^3 + 2(k+1)] - [k^3 + 2k]

= [k^3 + 2k^2 + 2k + 1 + 2k + 2] - [k^3 + 2k]

= 2k^2 + 2k + 3

which does not lead to a desirable expression.

I think I've exhausted all the options that I know of. Can anyone help me please?

2. Sep 29, 2005

### Tide

Note that $(n+1)^3 + 2(n+1) = n^3 + 3 n^2 + 5 n + 3 = n^3 + 2 n + 3(n^2 + n + 1)$

Therefore, if $n^3 + 2n$ is divisible by 3 then so is $(n+1)^3 + 2(n+1)$

3. Sep 29, 2005

### Tide

P.S. This is not by induction but I noticed that

$$n^3 + 2 n = n^3 + 3 n^2 + 2 n - 3n^2 = n(n+1)(n+2) - 3n^2$$

Since n is an integer then one of n, n+1 and n+2 must be divisible by 3 as is $3n^2$ so the original expression is divisible by 3 as well.

4. Sep 29, 2005

### waterchan

Arrrrgh damn it, no wonder I couldn't get it right. I got the binomial expansion wrong! Thanks a lot, Tide, and that's a neat second proof. Can't believe I wasted a couple hours due to a stupid slip-up...

Last edited: Sep 29, 2005
5. Sep 29, 2005

### waterchan

Another one I absolutely could not do (and this time I'm sure it's not due to fumbling algebra) is this:

Prove by induction that (1 + 1/4 + 1/9 + ... + 1/n^2) is less than (2 - 1/n) for all integers greater than 1.

I get the base step, then make the assumption p(k) is true. Then I add 1/(k+1)^2 to both sides of the inequality.

(1 + 1/4 + 1/9 + ... + 1/k^2 + 1/(k+1)^2) < 2 - 1/k + 1/(k+1)^2

I guess the desired result is to prove that the RHS is less than 2 - 1/(k+1), but I cannot achieve that at all. This one seems definitely more difficult than the last one. Can anybody help me please?

6. Sep 30, 2005

### Tide

Does this help?

$$-\frac {1}{k} + \frac {1}{(k+1)^2} < -\frac {1}{k} + \frac {1}{k+1}$$

7. Sep 30, 2005

### waterchan

Thanks a lot, Tide. Actually I got something similar to that, and THEN gave up, not sure how to proceed. Induction sure is a great way to get stuck :(

8. Sep 30, 2005

### Tide

Actually, induction is the easy part! Someone else did the grunt work of figuring out the appropriate inequality in the first place.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?