Proof by induction

  • Thread starter Firepanda
  • Start date
  • #1
430
0
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
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,836
251
Hi Firepanda! :smile:

Start "assume it's true for r ≤ n", and then try to prove it for r = n+1. :wink:
 
  • #3
430
0
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
tiny-tim
Science Advisor
Homework Helper
25,836
251
No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied? :confused:
 
  • #5
D H
Staff Emeritus
Science Advisor
Insights Author
15,415
687
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
430
0
No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied? :confused:

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
D H
Staff Emeritus
Science Advisor
Insights Author
15,415
687
There are three cases:
  • a|b1 and a|b2b3...br (game over), or
  • a|b1 (game over), or
  • a|b2b3...br.

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
tiny-tim
Science Advisor
Homework Helper
25,836
251
I don't think tiny-tim's idea will work because there is no base case to make the stack of dominos fall.

I was thinking of saying a|bbn+1 where b = b1…bn :wink:
 
  • #9
D H
Staff Emeritus
Science Advisor
Insights Author
15,415
687
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
tiny-tim
Science Advisor
Homework Helper
25,836
251
No, if a|bbn+1, then … :wink:
 
  • #11
430
0
No, if a|bbn+1, then … :wink:

go on... wanna see how you've done it!
 
  • #12
tiny-tim
Science Advisor
Homework Helper
25,836
251
Apply the induction … a divides the product of two numbers, so … ?
 
  • #13
430
0
Apply the induction … a divides the product of two numbers, so … ?

a|b or a|bn+1?
 
  • #14
tiny-tim
Science Advisor
Homework Helper
25,836
251
That's right. :smile:

Now carry on …​
 
  • #15
430
0
That's right. :smile:

Now carry on …​

dont we just conclude that i is certainly contained between 1 and n+1 inclusive so the induction hypothesis is true?
 
  • #16
tiny-tim
Science Advisor
Homework Helper
25,836
251
"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
430
0
"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)

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
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
884
  • Last Post
Replies
2
Views
779
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
939
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
9
Views
1K
Top