Ugh I am confused over tiny technical details..(Original post by Matureb)
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.
So to prove something is divisible by 30, it would be 15 and 2 ?
for 18  2 and 9
for x  any two factors which multiply to give x ?
Or is it that one of the factors must always be 2 ?
eg to prove something is divisible by 60 can I use 10 and 6 or must I use 2 and 30, or will 4 and 15 also work ?
Proof By Induction for Divisibility Help Needed
Announcements  Posted on  

How proud of your uni are you? Take our survey for the chance to win a holiday!  09022016 


(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 
(Original post by miml)
In general if you want to prove x is divisible by y then you have to show x is divisible by each of the prime factors of y. 
60 = 2*2*3*5. To test if a nunber is divisible by 60 it must be divisible by (2*2), by 3 and by 5. I.e it must be divisible by 3, 4 and 5. Note, these are relatively prime.
You are right that 4 and 15 will do since if it is divisible by 15, then it is automatically divisible by 3 and 5.
10 and 6 would not do. 90 is divisible by 10 and 6 , but not by 60. 
Surely it would be easier to say
1) when n=k
assume n^3n is divisible by 6
2) when n=k+1
n^3+3n^2+2n
1)x4 + 2)x2 gives 4n^34n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
......................(divisible by 6).............................. .................(divisible by 6)
As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2). 
(Original post by Matureb)
60 = 2*2*3*5. To test if a nunber is divisible by 60 it must be divisible by (2*2), by 3 and by 5. I.e it must be divisible by 3, 4 and 5. Note, these are relatively prime.
You are right that 4 and 15 will do since if it is divisible by 15, then it is automatically divisible by 3 and 5.
10 and 6 would not do. 90 is divisible by 10 and 6 , but not by 60.
(Original post by Quip)
Surely it would be easier to say
1) when n=k
assume n^3n is divisible by 6
2) when n=k+1
n^3+3n^2+2n
1)x4 + 2)x2 gives 4n^34n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
......................(divisible by 6).............................. .................(divisible by 6)
As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2). 
(Original post by Quip)
Surely it would be easier to say
1) when n=k
assume n^3n is divisible by 6
2) when n=k+1
n^3+3n^2+2n
1)x4 + 2)x2 gives 4n^34n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
......................(divisible by 6).............................. .................(divisible by 6)
As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
Surely you want 2n^3 + 6n^2 + 4n to be divisible by 12, to show that our original expression is divisible by 6. 
(Original post by miml)
Might be missing something, but your argument only shows that the "equation 2" is divisible by 2?
Surely you want 2n^3 + 6n^2 + 4n to be divisible by 12, to show that our original expression is divisible by 6.
However, I've just realised that as I've already multiplied it by 2, this only shows that n^3 + 3n^2 + 2n is divisible by 3 and you're right I need to show 2n^3 + 6n^2 + 4n is divisible by 12. Sorry, my mistake (I've been on holiday too long and forgotten how to do maths) 
there are different cases to consider:
firstly, n^3n can be expressed as: n(n1)(n+1)
so, first, if n is divisible by 3, then n1 is divisible by2, so whole thing divisible by 6  nothing further needed there.
second thing you do is examine what happens when n is both odd and even: odd n=2k+1 for some k in Z  you find out, by factoring, that both expressions are divisible by 2,
3rd, you examine n when it`s NOT divisible by 3  by using in the expression, (then factoring it) both n=3k+1, and n=3k1 (this ensures thatyou encompass every number NOT divisible by 3)  you find that the expression n^31 when used with these values, simplifies to something with a factor of 3,
so you will have proved simultaneously that the expression has factors of both 2 and 3... 
(Original post by Hasufel)
there are different cases to consider:
firstly, n^3n can be expressed as: n(n1)(n+1)
so, first, if n is divisible by 3, then n1 is divisible by2, so whole thing divisible by 6  nothing further needed there.
second thing you do is examine what happens when n is both odd and even: odd n=2k+1 for some k in Z  you find out, by factoring, that both expressions are divisible by 2,
3rd, you examine n when it`s NOT divisible by 3  by using in the expression, (then factoring it) both n=3k+1, and n=3k1 (this ensures thatyou encompass every number NOT divisible by 3)  you find that the expression n^31 when used with these values, simplifies to something with a factor of 3,
so you will have proved simultaneously that the expression has factors of both 2 and 3...
To prove by induction that a number is divisible by some number, the difference between k and k+1 must be used. Otherwise its just a direct proof.
(Original post by BJack)
. 
How I would have done it, if it had to be done by induction:
Assume true for n=k then is divisible by 6.
For n=k+1
The first bracket is divisible by 6 by our assumption so it remains to show the second bracket is.
Which is clearly divisible by 3, and as it contains a product of two consecutive numbers i.e. one must be even, it is also divisible by 2. Hence divisible by 6 and we have shown that for n=k+1 the expression is divisible by 6.
If it didn't have to be done by induction
Spoiler:Shown^3  n = (n1)n(n+1) which is the product of 3 consecutive integers, hence is divisible by 3 and 2 
(Original post by hassi94)
Also a problem with your idea of just showing either number is a multiple of 6 is that it isn't induction. You can do all the induction steps to disguise it as induction, but unless you actually use the assumption that n³  n is a multiple of 6 then its just a direct proof.
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: