Math 310 Solutions to Homework 3

1. Write a direct proof to show that for all integers n, n^2 + n is even.

PROOF:

This is a direct proof by cases. Since we defined an odd integer to be one
which not even, any integer n is either odd or even.

Case 1: Suppose n is even. Then n = 2k for some integer k, so

Since k(2k + 1) is an integer, this shows that n^2 + n is even.

Case 2: Suppose now that n is odd. Then n = 2k+1 for some integer k, so that

Hence, again, n^2 + n is even

This shows that for all possible integers n, the integer n^2 + n must be even

2. Let m and n be two arbitrary integers. Show that the product mn is odd if and
only if both m and n are odd.

PROOF:

We need to show that each of the fol lowing two implications hold:

1) ”<=”: If both m and n are odd, then mn is odd.

Since m and n are odd, we can write them as m = 2k+1 and n = 2l+1 for some
integers k and l. Hence mn = (2k +1)(2l +1) = 4kl +2k +2l +1 = 2(2kl +k +l)+1.
Since integers are closed under addition and multiplication , 2kl + k + l is an
integer, so mn is odd.

2) ”=>”: If mn is odd the both m and n must be odd.

It’s easiest to prove this by proving its contrapositive: if either m or n are not
odd (are even), then mn is not odd (is even). [Note: Recall that the negation
of ”P and Q” is ”not P OR not Q”!]

Suppose that at least one of m or n is even . Say, m is even, so m = 2k for some
integer k. Then mn = (2k)n = 2(kn) so mn is even. This proves the contrapositive
of the desired implication, and hence it also proves the implication itself.
QED

3. a) Give a counterexample to show that x≤y -> x^2≤y^2 is not always true.

Example: Let x = −2, y = 1. Then x≤y, but x^2 = 4 > y^2 = 1.

b) Prove that for all positive real numbers x and y,

PROOF:

We’ll prove the contra positive statement : for all positive real numbers x and y ,

Suppose x and y are two positive integers satisfyingBy Proposition
3.1.1 (review its proof!), it follows thatThis proves
the contrapositive and, since the contrapositive is logically equivalent to the
original implication, it also proves the desired result.

4. Prove that if x is a rational number and y is an irrational number, then their
sum x+y is an irrational number.

PROOF:

Suppose, by contradiction, that there exists a rational number x and an irrational
number y such that their sum x + y is a rational number.

By definition of ”rational number”, there exist integers a, b, c, and d, with b
and d non- zero , such that x = a/b and

That is,

Subtracting x = a/b from both sides and bringing the fractions to a common denominator :

Since bc−ad and bd are integers, and bd ≠ 0, this shows that y must be a rational,
which contradicts y being an irrational number.

This proves that x + y must be irrational. QED

5. Page 54, Problem 11
Prove by contradiction that there does not exist a smallest positive real number.

PROOF:

Suppose, by contradiction, that there exists a smallest positive real number
x. Since x is positive, so is x/2 ( divide both sides of x > 0 by 2, using the
Multiplication Law ). Also, x > x/2, because x − x/2 = x/2 > 0 (or, multiplying
1 > 1/2 by positive number x). But this proves that x/2 is a positive real
number which is smaller than x, which contradicts the assumption that x is
the smallest such number. This proves that our initial assumption was false,
so there is no smallest positive real number. QED

ALT PROOF:

Suppose, by contradiction, that there exists a smallest positive real number x.
We know such a number must be less than 1 (because there exist positive real
numbers less than 1, for example 1/2). So, 0 < x < 1. Multiplying throughout
by the positive number x, we get 0 < x^2 < x ( Multiplicative Law ). This shows
that the number x^2 is a positive real number less than x, which contradicts the
assumption that x is the smallest such number. Hence our initial assumption
was false, so there is no smallest positive real number. QED

REMARK: If you use a statement that is not always true (but maybe it happens
to be true in the context of your problem), you need to indicate what
makes it true in the specific problem. For instance, the statement x > x/2 is
not true for all x (ex: −3 −1.5) In this problem, it does happen to be true,
but you have to show why ( like indicated in the proof above).

6. Page 54, Pbl 12
Prove by induction on n that, for all positive integers n, 3 divides 4^n + 5.

PROOF:

Let P(n) denote the statement ”3 divides 4^n + 5”. We want to prove that P(n)
is true for all n ≥ 1.

1. Base Case n = 1: Since 4^1 + 5 = 9 and 3 divides 9, the base case is verified.

2. Induction Step : Suppose P(k) is true for some integer k ≥ 1. That is,
4^k+5 = 3a for some integer k ≥ 1 and some integer number a. We want to show
that 3 must also divide 4^k+1 + 5.

Rewriting 4^k+1 + 5 and using the induction hypothesis:

This proves the induction step.

Since the statement is true for n = 1, and we showed that, if true for some
k ≥ 1, then it’s also true for k + 1, the statement must be true for all n ≥ 1.QED

7. Page 55, Pbl 16
Prove by induction in n that

for all positive integers n.

PROOF:

1. Base Case n = 1: Since

the base case holds.

2. Induction Step: Suppose the statement is true for some k ≥ 1. That is, assume that

Consider now the sum from 1 to k + 1, and separate it into the sum up to k, plus the remaining term for k + 1:

By induction hypothesis, this is equal to:

Bringing to the common denominator and cancelling (k+1) (note: k+1 ≠ 0 for
any k ≥ 1) we obtain the desired result:

Since the statement is true for n = 1, and we showed that, if true for some
k ≥ 1, then it’s also true for k + 1, the statement must be true for all n ≥ 1. QED

8. Page 54, Pbl 10
What is wrong with the following proof that 1 is the largest integer?

ANSWER:

The problem with this argument is that it starts with an unproven (and wrong)
assumption, namely that that there exists a largest integer n. The rest of the
argument is correct.

If you examine the truth table for an implication P => Q, you see that if the
conclusion Q is false, one of two things must be true: either the implication
itself is false, or the hypothesis P is false. In other words to draw a valid
conclusion, you need both valid deductions AND valid assumptions!

Here we have an argument of the form P => ... => Q. Examining each step
of the argument we see that all the implications are correct – but the proof
starts off by assuming something unproven, namely that there exists a largest
integer, and ends up proving something obviously false, namely that 1 is the
largest integer.

This argument can be viewed as a proof by contradiction of the fact that
there is no largest integer. Since we have a valid argument that ends up with
something verifiably false (i.e. 1 is the largest integer, which contradicts the
fact that, say, 5 is a larger integer), the initial assumption that there exists a
largest integer must be false.