187 – Midterm 2

Here is midterm 2. 

Solutions follow.

Problem 1 introduces a relation R on integers by saying that x\mathrel{R} y iff the difference between x and y is at most 3. In symbols, x\mathrel{R} y\Longleftrightarrow |x-y|\le3. The problem asks to determine whether R is transitive.

It is not. For a counterexample, consider 2,5,6. We have 2\mathrel{R}5 and 5\mathrel{R}6, but 2\not\mathrel{R}6.

Problem 2 lets A be the collection of finite subsets of a set X, and defines a relation R on A by setting x\mathrel{R}y iff |x\triangle y| is even. The problem is to show that R is reflexive and symmetric.

To prove reflexivity, let x be an arbitrary finite subset of X. Then x\triangle x=\emptyset, so |x\triangle x|=0. Since 0 is even, we conclude that x\mathrel{R} x.

To prove symmetry, let x,y be finite subsets of X such that |x\triangle y| is even. Since x\triangle y=y\triangle x, we have that |y\triangle x| is even, and y\mathrel{R}x.

Problem 3 informs us that P(n,m) is a property about integers n,m, and asks us to choose among a few options for what is needed to do in order to prove that “For every integer n, there exists an integer m such that P(n,m) is true.”

To do this, we need to start with an arbitrary integer n, and then find an integer m that makes P(n,m) true. Of course, if we choose a different n, it could be that the m that now works is different, i.e., it may well be that m depends on n. Of the options listed in the problem, it is (e) that precisely captures this.

Note that if one manages to show (a) or (f), then one also succeeds in proving the required statement. However, both (a) and (f) are too strong in general, i.e., there are cases where the given statement holds but both (a) and (f) fail. None of the other options even guarantees the truth of the statement.

Problem 4 gives as an erroneous proof, and requires to identify the flaw. The statement being claimed is that all natural numbers are divisible by 3. The argument uses the well-ordering principle, and contradiction. Assuming that the statement is false means that there are natural numbers not divisible by 3. Letting X be the set of all these numbers, this means that X\ne\emptyset. The well-ordering principle guarantees that there is a least element of X, and we call it x. 

Clearly, x is not divisible by 3, so in particular x\ne0,3,6,\dots

The argument then asks to consider x-3. Obviously, x-3<x, and therefore x-3 is not in X. If x-3 happens to be a natural number, then we are forced to conclude that 3|(x-3) and therefore 3|x, since x=(x-3)+3. However, there is also the chance that x-3\notin{\mathbb N}, in which case we cannot conclude that 3|(x-3). Thus, we cannot conclude that 3|x. The flaw in the argument, of course, is in assuming that 3|(x-3), which is only assured if x-3\in{\mathbb N}.

Problem 5 asks to prove by induction that, for all positive integers n, we have

\displaystyle 1+\frac12+\frac13+\frac14+\dots+\frac1{2^n}\ge1+\frac{n}2.

To argue by induction, we first prove the base case, when n=1. We have 1+\frac12 on the left hand side and 1+\frac12 on the right hand side as well. The inequality holds (in fact, it is an equality in this case).

Now we argue the inductive step. Assume that, indeed, 

\displaystyle 1+\frac12+\frac13+\frac14+\dots+\frac1{2^n}\ge1+\frac{n}2.

We need to prove that also

\displaystyle 1+\frac12+\frac13+\frac14+\dots+\frac1{2^{n+1}}\ge1+\frac{n+1}2.

To do this, note that \displaystyle 1+\frac12+\frac13+\frac14+\dots+\frac1{2^{n+1}} \displaystyle= \bigl(1+\frac12+\frac13+\frac14+\dots+\frac1{2^n}\bigr) \displaystyle +\bigl(\frac1{2^n+1}+\frac1{2^n+2}+\dots+\frac1{2^{n+1}}\bigr). 

The sum inside the first set of parentheses is at least 1+\frac{n}2, by the inductive assumption. We are done if we manage to show that the sum within the second set of parentheses is at least \frac12. 

But note that \frac1{2^n+1}\ge\frac1{2^{n+1}}, \frac1{2^n+2}\ge\frac1{2^{n+1}}, etc, so the second sum is at least 

\displaystyle \frac1{2^{n+1}}+\frac1{2^{n+1}}+\dots+\frac1{2^{n+1}},

where there are precisely 2^n many terms being added, all of them equal to \displaystyle\frac1{2^{n+1}}. This means that this sum adds up to \displaystyle\frac{2^n}{2^{n+1}}=\frac12. Since this is what we needed, we have completed the inductive step, and therefore the proof.

Advertisement

This entry was posted on Wednesday, March 24th, 2010 at 1:01 pm and is filed under 187: Discrete mathematics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: