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

[Aidan1]

Homework Statement

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

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.

 

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

 

[D H]

No no no... You shouldn't instantly jump to f(k+1)-f(k) to try and prove this.

Why not? It works quite nicely.

f(k+1)-f(k) = 3k^2 + 3k +6

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

 

[Mentallic]

Why not? It works quite nicely.

What is the reasoning behind taking that approach?

 

[Aidan1]

What does modulo mean?

 

[D H]

What is the reasoning behind taking that approach?

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.

 

[D H]

What does modulo mean?

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

 

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

What does modulo mean?

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.