Prove That At Least 1 Integer Divides Another w/ Discrete Math

In summary: The Attempt at a SolutionLet P(n) be the claim that there will be two integers (x,\,y) such that y divides x.\left{1,\,2,\,\dots,\,2\,n\right} <----- Choose only n\,+\,1 of these.Basis: Does P(1) hold?\left{1,\,\dots,\,2\,n\right}\,=\,\left{1,\,2\right} <----- for n\,=\,12 is divisible by 1, so x = 2 and
  • #1
VinnyCee
489
0

Homework Statement



Use mathematical induction to show that given a set of [itex]n\,+\,1[/itex] positive integers, none exceeding [itex]2\,n[/itex], there is at least one integer in this set that divides another integer in the set.



Homework Equations



Mathematical induction, others, I am not sure



The Attempt at a Solution



Let [itex]P(n)[/itex] be the claim that there will be two integers [itex](x,\,y)[/itex] such that y divides x.

[tex]\left{1,\,2,\,\dots,\,2\,n\right}[/tex] <----- Choose only [itex]n\,+\,1[/itex] of these.

Basis: Does [itex]P(1)[/itex] hold?

[tex]\left{1,\,\dots,\,2\,n\right}\,=\,\left{1,\,2\right}[/tex] <----- for [itex]n\,=\,1[/itex]

2 is divisible by 1, so x = 2 and y = 1. [itex]P(1)[/itex] is true.


Inductive hypothesis:

[tex]\left{1,\,2,\,\dots,\,2\,n,\,2\,n\,+\,1,\,2\,n\,+\,2\right}[/tex] <----- Choose only [itex]n\,+\,2[/itex] of these

How do I prove that though?
 
Physics news on Phys.org
  • #2
Here's the start of a proof...

Let m be the largest integer in the set of n+1 integers.

If m <= 2(n-1), there are n integers in the set less than 2(n-1) , so by induction P(n) is true.

Now think about the cases where m = 2n-1 or m = 2n.
 
  • #3
By the way- there is no requirement that the n integers be distinct. In the n= 1 case, the two integers may be {1, 2}, {1, 1} or {2,2}. Of course, if they are NOT distinct, then obviously one of the duplicates divides the other so you really only need to consider the case that they are distinct- but you should say that.
 
  • #4


Resurrecting old thread, I also really need help with this problem. I'm completely lost, I couldn't even come with what the OP got on my own.

Thanks anyway
 
  • #5


By the way- there is no requirement that the n integers be distinct.

I believe there is that requirement, as the claim states that it is a set of positive integers. Sets contain unique elements.

Since Induction in general was part of your question, I would recommend looking at inductiveproofs.com -- they have a nice template for writing inductive proofs that you might find helpful.

Does the question hint at using weak or strong induction? (if you haven't heard of strong induction yet, that is helpful :) since we know it should use weak then!) The thing to think about is how can we get back to the smaller subset? AKA In the inductive step, we have a set of n+2 elements, all no higher than 2n+2, how do we talk about a subset of n+1 elements all no higher than 2n? What do we know about the other sets that don't contain that subset?
 

What is discrete math and how does it relate to proving integer division?

Discrete math is a branch of mathematics that deals with discrete objects and structures, such as integers. It is often used to prove properties and relationships in various areas of mathematics, including integer division.

What does it mean for one integer to divide another?

When one integer, also known as the divisor, divides another integer, also known as the dividend, the result is a whole number without any remainder. In other words, the division is exact.

How can you prove that at least one integer divides another?

One way to prove this is by using the division algorithm, which states that given any two integers a and b, where b is not equal to zero, there exist unique integers q and r such that a = bq + r, where 0 ≤ r < |b|.

What is the significance of proving that at least one integer divides another?

Proving that at least one integer divides another is important because it allows us to understand the properties and relationships of integers and their divisions. It also helps us to solve problems involving integers and identify patterns within them.

Are there any exceptions to the rule that at least one integer divides another?

Yes, there are exceptions such as division by zero, which is undefined, and cases where the dividend and divisor are both zero, resulting in an infinite number of possible quotients. In these cases, the division is not considered valid and cannot be proven.

Similar threads

  • Calculus and Beyond Homework Help
Replies
6
Views
870
Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
455
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
466
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
983
Back
Top