Why Can't I Prove Divisibility Using Mathematical Induction?

[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?

 

[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)$

 

[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.

 

[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...

 

[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?

 

[Tide]

Does this help?

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

 

[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 :(

 

[Tide]

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