# Proving that n(n^2+5) is divisible by 6

1. Nov 4, 2012

### Aidan1

1. The problem statement, all variables and given/known data

Prove by induction that $n (n^2 +5)$ is divisible by 6 for all positive integers $n$

3. The attempt at a solution

Let $f(n) = n (n^2 +5)$

$f(1) = 6$

So, true for $n=1$

Assume true for $f(k)$

For $n = k + 1$:

$f(k+1) = (k+1)[(k+1)^2 +5]$
$f(k+1)-f(k) = (k+1)(k^2 +2k +6) - k^3 + 5k$
$f(k+1)-f(k) = k^3 + 2k^2 + 6k +k^2 + 2k + 6 - k^3 -5k$
$f(k+1)-f(k) = 3k^2 + 3k +6$

I'm totally stuck from here. I was expecting f(k+1) - f(k) to be divisible by six, so then f(k+1) would be equal to the sum of two numbers divisible by six, which would show that f(k+1) is divisible by six. How can I show that final term is divisible by six? Or have I made a dumb mistake somewhere? Thanks.

Last edited: Nov 4, 2012
2. Nov 4, 2012

### Mentallic

No no no... You shouldn't instantly jump to f(k+1)-f(k) to try and prove this. To prove this divisibility problem, you need to do something more with your assumption:

Since
$$f(k)=k(k^2+5)$$
and is divisible by 6 by assumption, then we have that
$$f(k)=6N$$ for some integer N. We will be using this substitution in our proof.

Now, by working with f(k+1) we want to try and get it into a format such that we can directly substitute $k(k^2+5)=6N$ in.

So we have that

$$f(k+1)=(k+1)((k+1)^2+5)$$

Now you should expand completely, then you'll need to rearrange things to make it something like f(k+1)=f(k) + ...

3. Nov 4, 2012

### D H

Staff Emeritus
Why not? It works quite nicely.

Take both sides modulo 6. Obviously the +6 term on the right hand side contributes nothing. Can you take it from there?

4. Nov 4, 2012

### Mentallic

What is the reasoning behind taking that approach?

5. Nov 4, 2012

### Aidan1

What does modulo mean?

6. Nov 4, 2012

### D H

Staff Emeritus
A constructive proof that finds some integer $a_n$ such that $f(n) \equiv n(n^2+5) = 6a_n$ certainly is one way to solve this problem. There are other ways. Another approach is to use the fact that a number $n$ divides some number $a$ iff $a = 0 \mod n$. In other words, all one has to do solve this problem is to show that $f(n) \equiv n(n^2+5) = 0 \mod 6$.

I don't want to post my solution here in this thread; this is a homework question after all. I sent my solution as a PM to you instead. Read your private messages.

7. Nov 4, 2012

### D H

Staff Emeritus
Essentially it means remainder. For example $20\bmod6=4$ because dividing 20 by 6 leaves a remainder of 4.

Another way of saying that some number n divides some other number a is that $a\bmod n = 0$ (dividing a by n has a remainder of 0).

8. Nov 4, 2012

### Mentallic

DH, the proof you sent me is essentially what I would've done as well, minus the use of modulo and instead using the technique I posted in post #2 which is more intuitive for the younger Mathematicians, especially considering:

Anyway, the reason I don't like instantly finding f(k+1) - f(k) is because it doesn't seem to have any reasoning to back it up. Why have you chosen to evaluate this expression? Now even though you'll end up evaluating that expression eventually, it doesn't justify the leap of faith you have to take to evaluate it straight away.