# Proof by induction

1. May 9, 2010

### Firepanda

Use the method of induction to prove that if a ∈ Z is a prime
integer and if a/b1b2...br then a/bi for some 1 ≤ i ≤ r

I could prove this in other ways but how do you do this by induction?

I'm only use to induction of the form 'assume true for n show (n+1) also holds true'

Could someone start me of? Thanks

2. May 9, 2010

### tiny-tim

Hi Firepanda!

Start "assume it's true for r ≤ n", and then try to prove it for r = n+1.

3. May 9, 2010

### Firepanda

ok so..

a/b1b2...br then a/bi for some 1 ≤ i ≤ r

assume true for r ≤ n

a/b1b2...bn then a/bi for some 1 ≤ i ≤ n

if r = n+1

a/b1b2...bnbn+1 then a/bi for some 1 ≤ i ≤ n+1

but since we already had 1 ≤ i ≤ n then surely this is true?

Probably wrong

4. May 9, 2010

### tiny-tim

No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied?

5. May 9, 2010

### D H

Staff Emeritus
Work backwards. There are three cases:
• a|b1 and a|b2b3...br (game over), or
• a|b1 (game over), or
• a|b2b3...br.
In the last case, recurse.

I don't think tiny-tim's idea will work because there is no base case to make the stack of dominos fall.

6. May 9, 2010

### Firepanda

if a|bc and gcd(a,b) = 1 since a is prime and b certainly isn't as its a product

then a|c, so since a|c then a|bn+1, and 1 ≤ i ≤ n+1 so this holds true?

^ sorry this is wrong gcd(a,b) isnt 1 its bi

im stumped

7. May 9, 2010

### D H

Staff Emeritus
Conceptually, there are four cases:
1. a divides b1 and b2b3...br.
2. a divides b1 but not b2b3...br.
3. a divides b2b3...br but not b1
4. a divides neither b1 nor b2b3...br.
You need to show that these are the only four cases, and that case (4) does not apply.

8. May 9, 2010

### tiny-tim

I was thinking of saying a|bbn+1 where b = b1…bn

9. May 9, 2010

### D H

Staff Emeritus
So what is the base case? You do not know that a|b1.

You have proved that if a|b2b3...br then a|b2b3...brbr+1. The OP needs to prove the converse (assuming a does not divide br+1; it's game over if a|br+1).

10. May 9, 2010

### tiny-tim

No, if a|bbn+1, then …

11. May 9, 2010

### Firepanda

go on... wanna see how you've done it!

12. May 9, 2010

### tiny-tim

Apply the induction … a divides the product of two numbers, so … ?

13. May 9, 2010

### Firepanda

a|b or a|bn+1?

14. May 9, 2010

### tiny-tim

That's right.

Now carry on … ​

15. May 9, 2010

### Firepanda

dont we just conclude that i is certainly contained between 1 and n+1 inclusive so the induction hypothesis is true?

16. May 9, 2010

### tiny-tim

"i is certainly contained …"

That's meaningless!

What are you talking about? What is i?

(You're trying to find an i ≤ 1+1 such that a|bi, you haven't been given an i)

17. May 9, 2010

### Firepanda

but we assumed it was true?

ok then but we've shown a must divide one of the terms so a can divide at least one of the i ≤ n+1