Solutions to exercises in chapter 2 of the Discrete Math Zybook Exercise 2.2.1: Proving conditional statements with direct proofs. Prove each of the following statements using a direct proof. (a) If n is an odd integer, then n2 is an odd integer. (Note: the definition of an odd integer is an integer that can be expressed as 2k + 1, where k is an integer.) Proof.Direct proof. Assume that n
...[Show More]

Solutions to exercises in chapter 2 of the Discrete Math Zybook

Exercise

2.2.1: Proving conditional statements with direct proofs.

Prove each of the following statements using a direct proof.

(a)

If n is an odd integer, then n2 is an odd integer.

(Note: the definition of an odd integer is an integer that can be expressed as 2k + 1, where k is an

integer.)

**Proof.**

Direct proof. Assume that n is an odd integer. We will show that n2 is also an odd integer.

Since n is odd, n = 2k + 1, for some integer k. Plug the expression for n into n2:

*n*2=(2*k*+1)2=4*k*2+4*k*+1=2(2*k*2+2*k*)+1n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1

Since k is an integer, then (2k2 + 2k) is also an integer. Since n2 = 2c + 1, where c = 2k2 + 2k is

an integer, then n2 is odd. ■

(b)

For any positive real numbers, x and y, *x*+*y*≥*xy*--√x+y≥xy.

**Proof.**

Direct proof. Assume that for real numbers, x and y, x > 0 and y > 0. We will show that

*x*+*y*≥*xy*--√x+y≥xy.

Since x > 0 and y > 0, then xy > 0. Also, x2 > 0 and y2 > 0. Therefore

*x*2+*xy*+*y*2>0.x2+xy+y2>0.

Taking the square root of both sides gives:

Note that the expression A > B means that A is strictly greater than B. The expression A ≥ B

means that either A > B or A = B. Therefore, if it is true that A > B, then it automatically follows

that A ≥ B.

(c)

If x is a real number and x ≤ 3, then 12 - 7x + x2 ≥ 0.

**Proof.**

Direct proof. Assume that for real number x, x ≤ 3. We will show that 12 - 7x + x2 ≥ 0.

Subtract x from both sides of the inequality 3 ≥ x to get 3 - x ≥ 0. Since 4 - x is one larger than 3

- x, then

■

(d)

The product of two odd integers is an odd integer.

**Proof.**

Direct proof. Assume that x and y are odd integers. We will show that xy is also an odd integer.

Since x is odd, x = 2k+1 for some integer k. Since y is odd, y = 2j+1 for some integer j. The

Since j and k are both integers, (2kj + j + k) is also an integer. Since xy can be expressed as 2

times an integer plus 1, xy is an odd integer.

■

(e)

If r and s are rational numbers, then the product of r and s is a rational number.

**Proof.**

Direct proof. Assume that r = a/b and s = c/d, where c ≠ 0 and d ≠ 0. We will show that rs is a

rational number.

Plugging in the values r = a/b and s = c/d to rs:

since a, b, c, and d are all integers, then ac and bd are

also integers. Therefore rs is equal to the ratio of two integers in which the denominator is not

zero which implies that rs is rational.

Exercise

2.4.1: Proofs by contradiction.

Give a proof for each statement.

(a)

If a group of 9 kids have won a total of 100 trophies, then at least one of the 9 kids has won at

least 12 trophies.

**Proof.**

Proof by contradiction. Suppose that each kid has less than 12 trophies and the total number of

trophies owned by all the kids is 100. If each kid has less than 12 trophies, the most trophies any

kid can have is 11. If there are 9 kids, then the total number of trophies is at most 9·11 = 99,

which contradicts the fact that the total number of trophies is 100. ■

(b)

If a person buys at least 400 cups of coffee in a year, then there is at least one day in which the

Proof by contradiction. Suppose that the person has bought less than two cups of coffee each day

and has also bought at least 400 cups of coffee in the year. If the person buys less than two cups

of coffee in a day, she has bought at most 1 cup of coffee each day. Since there are at most 366

days in a year, the total number of cups of coffee that the person could have bought is at most

366, which contradicts the assumption that the person has bought at least 400 cups of coffee in

the year. ■

(c)

The average of three real numbers is greater than or equal to at least one of the numbers.

**Proof.**

Proof by contradiction. We assume that there are three real numbers x1, x2, and x3 such that the

average of the three numbers is less than each of the three numbers. That is (x1 + x2 + x3)/3 <

■

(d)

2√323 is irrational.

You can use the following fact in your proof:

If n is an integer and n3 is even, then n is even.

(e)

There is no smallest integer.

**Proof.**

Proof by contradiction. Suppose that there is a smallest integer x. If x is an integer, then x - 1 is

contradicts the assumption that x is the smallest integer. Therefore, the assumption that there

exists a smallest integer is false. ■

(f)

There is no largest rational negative number.

**Proof.**

Proof by contradiction. Suppose that r is the largest rational negative number. Since r is rational r

= a/b, for some integers a and b such that b ≠ 0. If b is an integer and b ≠ 0, then 2b is also an

integer and 2b ≠ 0. The number a/2b is a rational number because it is the ratio of two integers

such that the denominator is non-zero.

By assumption, a/b is negative which means that a/b < 0. dividing both sides of the inequality by

Therefore a/2b is a negative rational number that is larger than a/b which contradicts the

assumption that a/b is the largest negative rational number. The assumption that there exists a

largest negative rational number is false. ■

(a)

If x is an integer, then x2 + 5x - 1 is odd.

**Proof.**

We consider two cases: x is even and x is odd.

Since k is an integer, (2k2 + 5k - 1) is also an integer. Therefore, x2 + 5x - 1 is equal to 2 times an

integer plus 1 and x2 + 5x - 1 is odd.

**Case 2: **x is odd. If x is odd, then x = 2k + 1 for some integer k.

Since k is an integer, (2k2 + 7k +2) is also an integer. Therefore, x2 + 5x - 1 is equal to 2 times an

integer plus 1 and x2 + 5x - 1 is odd.

■

(b)

If x and y are real numbers, then max

**Proof.**

We consider two cases: x ≤ y and x > y

(c)

If integers x and y have the same parity, then x + y is even.

The parity of a number tells whether the number is odd or even. If x and y have the same parity,

they are either both even or both odd.

**Proof.**

We consider two cases: x and y are both even and the case in which x and y are both odd.

**Case 1: **x and y are both even. Since x and y are both even, then x = 2k and y = 2j for some

**Case 2: **x and y are both odd . Since x and y are both odd, then

some integers k and j. Then

Since x + y is a multiple of 2, then x + y is even. ■

(d)

For any real number x

(e)

For any real number x

You can use the fact proven in the previous problem that for any real number x, |x| ≥ 0.

**Proof.**

We consider two cases: x < 0 and x ≥ 0.

**Case 1: **x < 0. We can put the two inequalities |x| ≥ 0 and x < 0 together to get x < 0 ≤ |x|.

Therefore x ≤ |x|.

Since x < 0, by definition of absolute value, |x| = -x. Therefore it is also true that -x ≤ |x|.

**Case 2: **x ≥ 0. Since x ≥ 0, -x ≤ 0. We can put the inequality -x ≤ 0 together with the fact that |x|

≥ 0 to get that -x ≤ 0 < |x|. Therefore -

Since x ≥ 0, by definition of the absolute value, |x| = x. Therefore it is also true that x ≤ |x|. ■

(f)

For real numbers x and y, |

You can use the fact proven in the previous problem that for any real number z, z ≤ |z| and -z

**Proof.**

We consider two separate cases: x + y < 0 and x + y ≥ 0.

**Case 1: **x + y < 0. Then

**Case 2: **x + y ≥ 0. Then

■

(g)

For integers x and y, if xy is odd, then x is odd and y is odd.

**Proof.**

Proof by contrapositive. We assume that x and y are integers such that it is not true that x is odd

and y is odd and we will prove that xy is even. If it is not true that x is odd and y is odd, then by

De Morgan's law, x is not odd or y is not odd. We consider the two cases: in the first case x is

even and in the second case y is even.

**Case 1: **x is an integer and x is not odd. Therefore, x is even, and x = 2k for some integer k. Then

xy = 2ky. Since k and y are both integers, ky is also an integer. Since xy is an integer multiple of

2, xy is even.

**Case 2: **y is an integer and y is not odd. Therefore, y is even, and y = 2k for some integer k. Then

xy = 2kx. Since k and x are both integers, kx is also an integer. Since xy is an integer multiple of

2, xy is even. ■

(h)

Let x and y be two integers. If xy is not an integer multiple of 5, then neither x nor y is an integer

multiple of 5.

**Proof.**

Proof by contrapositive. We assume that x and y are integers and it is not the case that x is not an

an integer multiple of 5 or y is an integer multiple of 5. We consider each of these

cases separately.

**Case 1: **x is an integer multiple of 5. Therefore x = 5k for some integer k. Then xy = 5ky. Since k

and y are both integers, ky is also an integer. Therefore xy is an integer multiple of 5.

**Case 2: **y is an integer multiple of 5. Therefore y = 5k for some integer k. Then xy = 5kx. Since

k and x are both integers, kx is also an integer. Therefore xy is an integer multiple of 5. ■

[Show Less]