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

  • Thread starter Aidan1
  • Start date
  • #1
3
0

Homework Statement



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

The Attempt at a Solution



Let [itex] f(n) = n (n^2 +5) [/itex]

[itex] f(1) = 6 [/itex]

So, true for [itex] n=1 [/itex]

Assume true for [itex] f(k) [/itex]

For [itex] n = k + 1 [/itex]:

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

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:

Answers and Replies

  • #2
Mentallic
Homework Helper
3,798
94
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
[tex]f(k)=k(k^2+5)[/tex]
and is divisible by 6 by assumption, then we have that
[tex]f(k)=6N[/tex] 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 [itex]k(k^2+5)=6N[/itex] in.

So we have that

[tex]f(k+1)=(k+1)((k+1)^2+5)[/tex]

Now you should expand completely, then you'll need to rearrange things to make it something like f(k+1)=f(k) + ...
 
  • #3
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
686
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.

[itex] f(k+1)-f(k) = 3k^2 + 3k +6 [/itex]
Take both sides modulo 6. Obviously the +6 term on the right hand side contributes nothing. Can you take it from there?
 
  • #4
Mentallic
Homework Helper
3,798
94
Why not? It works quite nicely.
What is the reasoning behind taking that approach?
 
  • #5
3
0
What does modulo mean?
 
  • #6
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
686
What is the reasoning behind taking that approach?
A constructive proof that finds some integer [itex]a_n[/itex] such that [itex]f(n) \equiv n(n^2+5) = 6a_n[/itex] certainly is one way to solve this problem. There are other ways. Another approach is to use the fact that a number [itex]n[/itex] divides some number [itex]a[/itex] iff [itex]a = 0 \mod n[/itex]. In other words, all one has to do solve this problem is to show that [itex]f(n) \equiv n(n^2+5) = 0 \mod 6[/itex].

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
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
686
What does modulo mean?
Essentially it means remainder. For example [itex]20\bmod6=4[/itex] 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 [itex]a\bmod n = 0[/itex] (dividing a by n has a remainder of 0).
 
  • #8
Mentallic
Homework Helper
3,798
94
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.
 

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

  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
19
Views
13K
Replies
4
Views
898
  • Last Post
Replies
8
Views
2K
Replies
4
Views
10K
Replies
8
Views
3K
Replies
7
Views
7K
Replies
5
Views
2K
Replies
6
Views
2K
Top