The Student Room Group

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 un=n3nu_n = n^3 - n and assume it is divisible by 6.

Therefor, un+1=n3+3n2+2nu_{n+1} = n^3 + 3n^2 + 2n

Thus, un+1un=3n2+3nu_{n+1} - u_n = 3n^2 + 3n

As we assumed unu_n was divisible by 6 and clearly 3n2+3n3n^2 + 3n is divisible by 6 (as 3 is a factor of 6) then this proves that un+1u_{n+1} 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
(edited 11 years ago)

Scroll to see replies

Reply 1
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 un=n3nu_n = n^3 - n and assume it is divisible by 6.

Therefor, un+1=n3+3n2+2nu_{n+1} = n^3 + 3n^2 + 2n

Thus, un+1un=3n2+3nu_{n+1} - u_n = 3n^2 + 3n

As we assumed unu_n was divisible by 6 and clearly 3n2+3n3n^2 + 3n is divisible by 6 (as 3 is a factor of 6) then this proves that un+1u_{n+1} 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
Reply 2
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 ?
Reply 3
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

Reply 4
Hint: n is either odd or even...
Reply 5
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 un=n3nu_n = n^3 - n and assume it is divisible by 6.

Therefor, un+1=n3+3n2+2nu_{n+1} = n^3 + 3n^2 + 2n

Thus, un+1un=3n2+3nu_{n+1} - u_n = 3n^2 + 3n

As we assumed unu_n was divisible by 6 and clearly 3n2+3n3n^2 + 3n is divisible by 6 (as 3 is a factor of 6) then this proves that un+1u_{n+1} 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
Reply 6
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. :s-smilie:
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. :s-smilie:


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).
Reply 8
Original post by hassi94
Well you've assumed Un is divisible by 6


Ah, yes. :redface:
Reply 9
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



n3+3n2+2n=n(n+1)(n+2)n^3 + 3n^2 + 2n = n(n+1)(n+2)

Now how do I show that this is divisible by 6 ?
Reply 10
Original post by member910132
n3+3n2+2n=n(n+1)(n+2)n^3 + 3n^2 + 2n = n(n+1)(n+2)

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?
Reply 11
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 3n2+3n=3n(n+1)3n^2 + 3n = 3n(n+1) 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) ?
Reply 12
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.
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.
Reply 14
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 :smile:
Reply 15
18 is divisible by 2 and by 6. But not by 12. Any number divisible by 6 will be divisible by 2.
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 :smile:


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.
Reply 17
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 ?
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 :smile:
Reply 19
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.

Quick Reply