200k views
2 votes
Prove for any positive integer n, n^3 +11n is a multiple of 6

User Nneka
by
5.5k points

1 Answer

2 votes

There are probably other ways to approach this, but I'll focus on a proof by induction.

The base case is that n = 1. Plugging this into the expression gets us

n^3+11n = 1^3+11(1) = 1+11 = 12

which is a multiple of 6. So that takes care of the base case.

----------------------------------

Now for the inductive step, which is often a tricky thing to grasp if you're not used to it. I recommend keeping at practice to get better familiar with these types of proofs.

The idea is this: assume that k^3+11k is a multiple of 6 for some integer k > 1

Based on that assumption, we need to prove that (k+1)^3+11(k+1) is also a multiple of 6. Note how I've replaced every k with k+1. This is the next value up after k.

If we can show that the (k+1)th case works, based on the assumption, then we've effectively wrapped up the inductive proof. Think of it like a chain of dominoes. One knocks over the other to take care of every case (aka every positive integer n)

-----------------------------------

Let's do a bit of algebra to say

(k+1)^3+11(k+1)

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

k^3+3k^2+3k+1+11k+11

(k^3+11k) + (3k^2+3k+12)

(k^3+11k) + 3(k^2+k+4)

At this point, we have the k^3+11k as the first group while we have 3(k^2+k+4) as the second group. We already know that k^3+11k is a multiple of 6, so we don't need to worry about it. We just need to show that 3(k^2+k+4) is also a multiple of 6. This means we need to show k^2+k+4 is a multiple of 2, i.e. it's even.

------------------------------------

If k is even, then k = 2m for some integer m

That means k^2+k+4 = (2m)^2+(2m)+4 = 4m^2+2m+4 = 2(m^2+m+2)

We can see that if k is even, then k^2+k+4 is also even.

If k is odd, then k = 2m+1 and

k^2+k+4 = (2m+1)^2+(2m+1)+4 = 4m^2+4m+1+2m+1+4 = 2(2m^2+3m+3)

That shows k^2+k+4 is even when k is odd.

-------------------------------------

In short, the last section shows that k^2+k+4 is always even for any integer

That then points to 3(k^2+k+4) being a multiple of 6

Which then further points to (k^3+11k) + 3(k^2+k+4) being a multiple of 6

It's a lot of work, but we've shown that (k+1)^3+11(k+1) is a multiple of 6 based on the assumption that k^3+11k is a multiple of 6.

This concludes the inductive step and overall the proof is done by this point.

User Dherik
by
5.7k points