Just one sec...
 You are Here: Home >< Maths

# Proof By Induction for Divisibility Help Needed

Announcements Posted on
Take our short survey, ยฃ100 of Amazon vouchers to be won! 23-09-2016
1. Prove by induction that n^3 - n is divisible by 6.

Would I get full marks if I have done this:

let and assume it is divisible by 6.

Therefor,

Thus,

As we assumed was divisible by 6 and clearly is divisible by 6 (as 3 is a factor of 6) then this proves that is divisible by 6.

For n=1 we have 1-1=0, which is divisible by 6.

I am not 100% sure on the part where I use the factor of 3 to show that it is divisible by 6, I couldn't get a 6 or a multiple of 6.
I would highly appreciate it if people could give me the general rule about if it is okay to use factors of the number we are trying to show it is divisible by and not the number itself or a multiple.
I am also unsure about the end where I say 0 is divisible by 6, is 0 a positive integer ?

Edit: I would highly appreciate some general advice about what to do after getting U(n) and U(n+1), I struggle to work out whether to add them, subtract them, add one to a multiple of another (which multiples can we use ?), can we multiply both U(n) and U(n+1) but different multiples......

Thnx
2. (Original post by member910132)
Prove by induction that n^3 - n is divisible by 6.

Would I get full marks if I have done this:

let and assume it is divisible by 6.

Therefor,

Thus,

As we assumed was divisible by 6 and clearly is divisible by 6 (as 3 is a factor of 6) then this proves that is divisible by 6.

For n=1 we have 1-1=0, which is divisible by 6.

I am not 100% sure on the part where I use the factor of 3 to show that it is divisible by 6, I couldn't get a 6 or a multiple of 6.
I would highly appreciate it if people could give me the general rule about if it is okay to use factors of the number we are trying to show it is divisible by and not the number itself or a multiple.
I am also unsure about the end where I say 0 is divisible by 6, is 0 a positive integer ?

Thnx
the bold statement seems dodgy... you could say 3 is a factor of 111 so the expression must be a multiple of 111
3. (Original post by the bear)
the bold statement seems dodgy... you could say 3 is a factor of 111 so the expression must be a multiple of 111
Good point lol, so what do I do ? I am beginning to think there is a typo in the question because of that last part about n=1 being divisible by 6 ? Is 0 divisible by any number ?
4. (Original post by member910132)
Edit: I would highly appreciate some general advice about what to do after getting U(n) and U(n+1), I struggle to work out whether to add them, subtract them, add one to a multiple of another (which multiples can we use ?), can we multiply both U(n) and U(n+1) but different multiples......
When doing the proof by induction, you want to say "assume true for n=k; then for n=k+1 we have ...". So you prove the ladder goes on; then you take your basis case to show the ladder has a bottom and you're done.

So after getting that the expression for n= k+1 is k3 + 3k2 + 2k, you simply need play with it in such a way to show that it's divisible by 6.

Spoiler:
Show
try factorizing it
5. Hint: n is either odd or even...
6. (Original post by member910132)
Prove by induction that n^3 - n is divisible by 6.

Would I get full marks if I have done this:

let and assume it is divisible by 6.

Therefor,

Thus,

As we assumed was divisible by 6 and clearly is divisible by 6 (as 3 is a factor of 6) then this proves that is divisible by 6.

For n=1 we have 1-1=0, which is divisible by 6.

I am not 100% sure on the part where I use the factor of 3 to show that it is divisible by 6, I couldn't get a 6 or a multiple of 6.
I would highly appreciate it if people could give me the general rule about if it is okay to use factors of the number we are trying to show it is divisible by and not the number itself or a multiple.
I am also unsure about the end where I say 0 is divisible by 6, is 0 a positive integer ?

Edit: I would highly appreciate some general advice about what to do after getting U(n) and U(n+1), I struggle to work out whether to add them, subtract them, add one to a multiple of another (which multiples can we use ?), can we multiply both U(n) and U(n+1) but different multiples......

Thnx
Slightly odd way of proving it (introducing the u_n I mean)

And as the poster above pointed out the bold bit isn't enough. In this case it is true as 3n^2+3n is always even. But the key thing is you need to show that n^3-n is divisible by both 3 and 2
7. (Original post by miml)
In this case it is true as 3n^2+3n is always even.
3n2 + 3n is the difference between consecutive terms n and n+1. You can conclude from this that the difference is divisible by 6; but that doesn't prove that (n3 - n) is itself divisible by 6.
8. (Original post by BJack)
3n2 + 3n is the difference between consecutive terms n and n+1. You can conclude from this that the difference is divisible by 6; but that doesn't prove that (n3 - n) is itself divisible by 6.
Well you've assumed Un is divisible by 6

And shown Un+1 - Un is divisible by 6. Therefore Un+1 = some multiple of 6 + some other multiple of 6 = multiple of 6

So it does prove it (but as miml said the OP does need to take a factor of 3 out, then show that what's remaining is in fact even - which is simple).
9. (Original post by hassi94)
Well you've assumed Un is divisible by 6
Ah, yes.
10. (Original post by BJack)
When doing the proof by induction, you want to say "assume true for n=k; then for n=k+1 we have ...". So you prove the ladder goes on; then you take your basis case to show the ladder has a bottom and you're done.

So after getting that the expression for n= k+1 is k3 + 3k2 + 2k, you simply need play with it in such a way to show that it's divisible by 6.

Spoiler:
Show
try factorizing it

Now how do I show that this is divisible by 6 ?
11. (Original post by member910132)

Now how do I show that this is divisible by 6 ?
What can you say about the divisibility of an integer and its two successors?
12. (Original post by miml)
Slightly odd way of proving it (introducing the u_n I mean)

And as the poster above pointed out the bold bit isn't enough. In this case it is true as 3n^2+3n is always even. But the key thing is you need to show that n^3-n is divisible by both 3 and 2
I don't fully understand why I need to show that it is divisible by 3 and 2 ?
If I was trying to prove something is divisible by 10 would I have to do 5 and 2 ? Is it always two of the factors ?

Secondly, how do I show is divisible by 3 and 2 ? Or how do i show it is even ?

Edit: can anyone address this thing about n=1 gives 0 and is 0 divisible by 6 (or any number) ?
13. (Original post by BJack)
What can you say about the divisibility of an integer and its two successors?
No clue, I am new to this type of maths.
14. As has been established the difference between consecutive terms is 3n(n+1)

If n is even then it can be written as 2p where p is an integer. Thus substitution brings 6p(2p+1) which is obviously a multiple of 6 for all p.

If n is odd then it can be expressed as 2q-1 where q is an integer. Substitution brings 6p(2p-1) which 6 also divides.

As when n=0 6 divides n^3-n the induction holds.

The key fact is that consecutive integers have at least one factor of 2.
15. (Original post by BJack)
What can you say about the divisibility of an integer and its two successors?
Oh, can we say that at least one of those numbers must be even and so the whole thing can be divided by 2 and so the whole number is even.

But can someone clarify this issue of using factors to prove something is divisible by a number ?
If I wanted to prove something is divisible by x, then obviously proving it is divisible by Ax would suffice right ? (where A is a constant integer).

But if I am to prove that something is divisible by 12 for example then must I say that it is divisible by 2 of it's factors, eg show that it is divisible by both 3 and 4 or 2 and 6 ?

Thnx tons
16. 18 is divisible by 2 and by 6. But not by 12. Any number divisible by 6 will be divisible by 2.
17. (Original post by member910132)
Oh, can we say that at least one of those numbers must be even and so the whole thing can be divided by 2 and so the whole number is even.

But can someone clarify this issue of using factors to prove something is divisible by a number ?
If I wanted to prove something is divisible by x, then obviously proving it is divisible by Ax would suffice right ? (where A is a constant integer).

But if I am to prove that something is divisible by 12 for example then must I say that it is divisible by 2 of it's factors, eg show that it is divisible by both 3 and 4 or 2 and 6 ?

Thnx tons
Yes member you can say that, but then you'll also have to note that in 3 consecutive numbers, one of those numbers must be divisible by 3.

However, I do prefer the method you began with (and almost finished in your original post) - it assumes less and is the standard method for these questions at A-level.

For the other 2 questions, yes if you can show it's divisible by say 12, it's obviously divisible by 6.

And yes you cannot say because it is divisible by 2 it must be divisible by 286 (essentially what you did in your original post), you must show it is divisible by all the factors required.
18. (Original post by Matureb)
18 is divisible by 2 and by 6. But not by 12. Any number divisible by 6 will be divisible by 2.
But to prove something is divisible by 18 is it sufficient to prove it is divisible by 2 and 6 ?
(Original post by hassi94)
Yes member you can say that, but then you'll also have to note that in 3 consecutive numbers, one of those numbers must be divisible by 3.

However, I do prefer the method you began with (and almost finished in your original post) - it assumes less and is the standard method for these questions at A-level.

For the other 2 questions, yes if you can show it's divisible by say 12, it's obviously divisible by 6.

And yes you cannot say because it is divisible by 2 it must be divisible by 286 (essentially what you did in your original post), you must show it is divisible by all the factors required.
What do you mean by all the factors required ? To prove something is divisible by x is it sufficient to show that it is divisible by any two factors of x or must these factors meet certain conditions ?
19. (Original post by member910132)
But to prove something is divisible by 18 is it sufficient to prove it is divisible by 2 and 6 ?

What do you mean by all the factors required ? To prove something is divisible by x is it sufficient to show that it is divisible by any two factors of x or must these factors meet certain conditions ?
Sorry to confuse you, yes what you said is sufficient. In this question its 2 and 3 as you've noticed
20. No. In this case 30 is divisible by 2 and by 6. But not by 18. For 18 you would need to show it was divisible by 2 and 9.

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. Oops, you need to agree to our Ts&Cs to register

Updated: April 17, 2012
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

### Justine Greening Q&A

Exam reform and more; post a question for the education secretary

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read here first

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams