You are Here: Home

Proof By Induction for Divisibility Help Needed Tweet

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
Enter our travel-writing competition for the chance to win a Nikon 1 J3 camera 20-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
1. Proof By Induction for Divisibility Help Needed
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
Last edited by member910132; 16-04-2012 at 13:27.
2. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
Hint: n is either odd or even...
6. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(Original post by hassi94)
Well you've assumed Un is divisible by 6
Ah, yes.
10. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
18 is divisible by 2 and by 6. But not by 12. Any number divisible by 6 will be divisible by 2.
17. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
(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. Re: Proof By Induction for Divisibility Help Needed
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.