The Student Room Group

Proof By Induction for Divisibility Help Needed

Scroll to see replies

Reply 20
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.


Ugh I am confused over tiny technical details..
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 ?
Reply 21
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:


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.
Reply 22
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.


Tank you so much for this !!!!!!!!!!
Reply 23
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.
Reply 24
Surely it would be easier to say

1) when n=k
assume n^3-n is divisible by 6

2) when n=k+1
n^3+3n^2+2n

1)x4 + 2)x2 gives 4n^3-4n + 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).
Reply 25
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.


Got it, great ! So I just need to shwo that it is divisible by it's prime factors or the prime factors multiplied by each other (in the example of 2.2.3.5 = 4.15)

Original post by Quip
Surely it would be easier to say

1) when n=k
assume n^3-n is divisible by 6

2) when n=k+1
n^3+3n^2+2n

1)x4 + 2)x2 gives 4n^3-4n + 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).


Sorry I can't follow what you have done at all, but it is okay, I get it now. And I realize that their are other ways of doing it but I wanted to know how to do it in a specific way.
Reply 26
Original post by Quip
Surely it would be easier to say

1) when n=k
assume n^3-n is divisible by 6

2) when n=k+1
n^3+3n^2+2n

1)x4 + 2)x2 gives 4n^3-4n + 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).


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.
Reply 27
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.


I thought that because it equals something that is divisible by 6 and equation 1 is divisible by 6 (assumed), the 2n^3 + 6n^2 + 4n must also be divisible by 6. (If two things are added which are both divisible by 6, the sum will also be 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)
Reply 28
there are different cases to consider:

firstly, n^3-n can be expressed as: n(n-1)(n+1)

so, first, if n is divisible by 3, then n-1 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=3k-1 (this ensures thatyou encompass every number NOT divisible by 3) - you find that the expression n^3-1 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...
(edited 11 years ago)
Original post by Hasufel
there are different cases to consider:

firstly, n^3-n can be expressed as: n(n-1)(n+1)

so, first, if n is divisible by 3, then n-1 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=3k-1 (this ensures thatyou encompass every number NOT divisible by 3) - you find that the expression n^3-1 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...


Problem with this is proof was asked to be done by induction.

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.

BJack
.


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 is a multiple of 6 then its just a direct proof.
(edited 11 years ago)
Reply 30
How I would have done it, if it had to be done by induction:
Assume true for n=k then k3k k^3 - k is divisible by 6.

For n=k+1 (k+1)3(k+1)=k3+3k2+3k+1k1=k3+3k2+2k=(k3k)+(3k23k) (k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = k^3 + 3k^2 +2k = (k^3 - k) + (3k^2 - 3k)

The first bracket is divisible by 6 by our assumption so it remains to show the second bracket is. 3k23k=3k(k+1) 3k^2 - 3k = 3k(k+1)
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

Reply 31
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 is a multiple of 6 then its just a direct proof.


Oh dear. :s-smilie:

Quick Reply

Latest