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 11=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
Proof By Induction for Divisibility Help Needed
Announcements  Posted on  

Study Help needs new mods!  14042014  
We're up for a Webby! Vote TSR to help us win.  10042014 


(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 11=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 
(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 
(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......
So after getting that the expression for n= k+1 is k^{3} + 3k^{2} + 2k, you simply need play with it in such a way to show that it's divisible by 6.
Spoiler:Showtry factorizing it 
Hint: n is either odd or even...

(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 11=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
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^3n is divisible by both 3 and 2 
(Original post by miml)
In this case it is true as 3n^2+3n is always even. 
(Original post by BJack)
3n^{2} + 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 (n^{3}  n) is itself 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). 
(Original post by hassi94)
Well you've assumed Un is divisible by 6 
(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 k^{3} + 3k^{2} + 2k, you simply need play with it in such a way to show that it's divisible by 6.
Spoiler:Showtry factorizing it
Now how do I show that this is divisible by 6 ? 

(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^3n is divisible by both 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) ? 
(Original post by BJack)
What can you say about the divisibility of an integer and its two successors? 
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 2q1 where q is an integer. Substitution brings 6p(2p1) which 6 also divides.
As when n=0 6 divides n^3n the induction holds.
The key fact is that consecutive integers have at least one factor of 2. 
(Original post by BJack)
What can you say about the divisibility of an integer and its two successors?
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 
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
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 Alevel.
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. 
(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.
(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 Alevel.
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. 
(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 ? 
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.
Reply
Submit reply
Register
Thanks for posting! You just need to create an account in order to submit the post Already a member? Sign in
Oops, something wasn't right
please check the following: