# Mathematical Induction

• Nov 21st 2009, 12:09 PM
oldguynewstudent
Mathematical Induction
Can anyone verify whether the following proof is correct or incorrect? If incorrect please explain where and why I went wrong?

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

S = { $x_i$ such that i = 1,2,...,n+1, $x_i$ $\le$ 2n}

Show that $\exists$ $x_i$ such that $x_i$ | $x_j$ i $\not=$ j

Basis Step: P(1): case 1: S={1,2} 1 | 2 so P(1) is true
case 2: S={1,1} 1 | 1 so P(1) is true

Inductive Step: P(k) $\Rightarrow$ P(k+1)

Given S = { $x_i$ such that i = 1,2,...,k+1, $x_i$ $\le$ 2k}
$\exists$ $x_i$ such that $x_i$ | $x_j$ i $\not=$ j

Prove that $\exists$ $x_s$ such that $x_s$ | $x_t$, s $\not=$ t
where $x_s$ $\epsilon$ { $x_i$ such that i = 1,2,...,k+1,(k+1)+1 $x_i$ $\le$ 2(k+1)}

Note that { $x_i$ such that i = 1,2,...,k+1,(k+1)+1 $x_i$ $\le$ 2(k+1)} = S $\cup$ { $x_i$ such that i = (k+1)+1 $x_i$ $\le$ 2(k+1)}

Choose $x_s$ = $x_i$ that divides $x_j$ and $x_t$ = $x_j$ from the given part.

This proves P(k+1) is true, so the original statement is true by M.I.
• Nov 21st 2009, 01:31 PM
Focus
Quote:

Originally Posted by oldguynewstudent
Can anyone verify whether the following proof is correct or incorrect? If incorrect please explain where and why I went wrong?

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

S = { $x_i$ such that i = 1,2,...,n+1, $x_i$ $\le$ 2n}

Show that $\exists$ $x_i$ such that $x_i$ | $x_j$ i $\not=$ j

Basis Step: P(1): case 1: S={1,2} 1 | 2 so P(1) is true
case 2: S={1,1} 1 | 1 so P(1) is true

Inductive Step: P(k) $\Rightarrow$ P(k+1)

Given S = { $x_i$ such that i = 1,2,...,k+1, $x_i$ $\le$ 2k}
$\exists$ $x_i$ such that $x_i$ | $x_j$ i $\not=$ j

Prove that $\exists$ $x_s$ such that $x_s$ | $x_t$, s $\not=$ t
where $x_s$ $\epsilon$ { $x_i$ such that i = 1,2,...,k+1,(k+1)+1 $x_i$ $\le$ 2(k+1)}

Note that { $x_i$ such that i = 1,2,...,k+1,(k+1)+1 $x_i$ $\le$ 2(k+1)} = S $\cup$ { $x_i$ such that i = (k+1)+1 $x_i$ $\le$ 2(k+1)}

Choose $x_s$ = $x_i$ that divides $x_j$ and $x_t$ = $x_j$ from the given part.

This proves P(k+1) is true, so the original statement is true by M.I.

It is not wrong per say, but the reasoning is a little off. For the P(k+1) case you want to make sure that you have a set of elements that are no greater than 2k, and have k elements. Here are the three possible cases.
Case 1:
Now if more than one element is 2k+1 or 2k+2, then P(k+1) is true as any number is divisible by itself.
Case 2:
If only one element or no element is greater than 2k then we can apply the induction hypothesis (by looking at the first k+1).
Case 3:
Precisely one element is 2k+1 and one 2k+2, in which case we have k elements that are less than or equal to 2k (we need k+1).
If we have 2 in our set, then 2|(2k+2) and we are done.
Suppose that 2 is not in our set and notice that for $a\neq 2$, a|(2k+2) iff a|(k+1), as 2 is prime. Also $k+1\leq 2k$. So replace the element 2k+2 by k+1, and you get k+1 elements that are less than 2k. Apply the inductive hypothesis to conclude this case.
• Nov 21st 2009, 01:54 PM
Defunkt
If you also wish to prove this not by induction, then you may do it this way:

Let $a_1,a_2,...,a_{n+1}$ be our numbers. Let us define a sequence $\{b_k\}_{k=1}^{n+1}$ as $b_i = a_i (mod \ n) \ \forall 1\leq i \leq n+1$.

Now, since there are only $n$ possible values for $b_i$ , from the pidgeonhole principle we get that at least two elements in that sequence must equal each other (since there are $n+1$ elements for $n$ possible values), and from that, one of them must divide the other.
• Nov 21st 2009, 03:18 PM
oldguynewstudent
I finally got it
Quote:

Originally Posted by Focus
It is not wrong per say, but the reasoning is a little off. For the P(k+1) case you want to make sure that you have a set of elements that are no greater than 2k, and have k elements. Here are the three possible cases.
Case 1:
Now if more than one element is 2k+1 or 2k+2, then P(k+1) is true as any number is divisible by itself.
Case 2:
If only one element or no element is greater than 2k then we can apply the induction hypothesis (by looking at the first k+1).
Case 3:
Precisely one element is 2k+1 and one 2k+2, in which case we have k elements that are less than or equal to 2k (we need k+1).
If we have 2 in our set, then 2|(2k+2) and we are done.
Suppose that 2 is not in our set and notice that for $a\neq 2$, a|(2k+2) iff a|(k+1), as 2 is prime. Also $k+1\leq 2k$. So replace the element 2k+2 by k+1, and you get k+1 elements that are less than 2k. Apply the inductive hypothesis to conclude this case.

Thanks so much for this! I've been going over it off and on for the past couple of hours and I've finally lit the led in my head!(Hi)

I've also been struggling with a stubborn home-made Macgyvered electrolysis experiment I cooked up for an inner city Chemistry class I'm observing for my sec ed class. It's been 35 years since I did chemistry and it shows. The chem teacher's specialty is Biology so I've been able to teach a couple of classes. I figured out my error there also, so things are looking up!
• Nov 21st 2009, 03:28 PM
Focus
Quote:

Originally Posted by oldguynewstudent
Thanks so much for this! I've been going over it off and on for the past couple of hours and I've finally lit the led in my head!(Hi)

I've also been struggling with a stubborn home-made Macgyvered electrolysis experiment I cooked up for an inner city Chemistry class I'm observing for my sec ed class. It's been 35 years since I did chemistry and it shows. The chem teacher's specialty is Biology so I've been able to teach a couple of classes. I figured out my error there also, so things are looking up!

Glad to hear that. Good luck with your studies. Hopefully you can spend the next 35 years doing maths (Evilgrin).