solution #5 - Arkansas Tech University

Arkansas Tech University
MATH 2703: Discrete Mathematics
Dr. Marcel B. Finan
Solution to Section 5
Problem 5.1
Using the method of vacuous proof, show that if n is a positive integer and
n = −n then n2 = n.
Solution.
If n is a positive integer then n > 0 and −n < 0. Thus, the statement n = −n
is false and by the method of vacuous proof, n2 = n is true
Problem 5.2
Show that for all x ∈ R, x2 + 1 < 0 implies x2 ≥ 4.
Solution.
Since x2 + 1 < 0 is false for all x ∈ R, the implication is vacuously true
Problem 5.3
Use the method of trivial proof to show that if x ∈ R and x > 0 then
x2 + 1 > 0.
Solution.
For all x ∈ R, we have x2 + 1 > x2 ≥ 0. Hence, x2 + 1 > 0. Note that the
implication is proves without using the hypothesis x > 0
Problem 5.4
Use the method of proof by cases to prove that for any integer n the product
n(n + 1) is even.
Solution.
We use the method of proof by cases.
Case 1. Suppose n is even. Then there is an integer k such that n = 2k.
Thus, n(n+1) = 2k(2k +1) = 2k 0 where k 0 = k(2k +1) ∈ Z. That is, n(n+1)
is even.
Case 2. Suppose that n is odd. Then there exists an integer k such that
n = 2k+1. So, n(n+1) = 2(2k+1)(k+1) = 2k 0 where k 0 = (2k+1)(k+1) ∈ Z.
Again, n(n + 1) is even
1
Problem 5.5
Use the method of proof by cases to prove that the square of any integer has
the form 4k or 4k + 1 for some integer k
Solution.
We use the method of proof by cases.
Case 1. Suppose n is even. Then there is an integer m such that n = 2m.
Taking the square of n we find n2 = 4m2 = 4k where k = m2 ∈ Z.
Case 2. Suppose n is odd. Then there is an integer m such that n = 2m + 1.
Taking the square of n we find n2 = 4m2 + 4m + 1 = 4(m2 + m) + 1 = 4k + 1
where k = m2 + m ∈ Z
Problem 5.6
Use the method of proof by cases to prove that for any integer n, n(n2 −
1)(n + 2) is divisible by 4.
Solution.
We use the method of proof by cases.
Case 1. Suppose n is even. Then there is an integer m such that n = 2m This
implies that n(n2 −1)(n+2) = 2m(4m2 −1)(2m+2) = 4m(4m2 −1)(m+1) =
4k where k = m(4m2 − 1)(m + 1) ∈ Z. Thus, n(n2 − 1)(n + 2) is divisible by
4.
Case 2. Suppose n is odd. Then there is an integer m such that n = 2m + 1.
Thus, n(n2 − 1)(n + 2) = (2m + 1)(4m2 + 4m)(2m + 3) = 4k where k =
(2m + 1)(m2 + m)(2m + 3) ∈ Z. Thus, n(n2 − 1)(n + 2) is divisible by 4
Problem 5.7
State a necessary and sufficient condition for the floor function of a real
number to equal that number.
Solution.
Theorem. bxc = x if and only if x ∈ Z.
Proof. Suppose that bxc = x. From the definition of the floor function, x ∈ Z. Conversely, if x ∈ Z then x is the smallest integer such that
x ≤ x < x + 1. That is, bxc = x
2
Problem 5.8
Prove that if n is an even integer then b n2 c = n2 .
Solution.
If n is an even integer then there is an integer k such that n = 2k. In this
case,
n
n
b c = bkc = k =
2
2
Problem 5.9
Show that the equality bx − yc = bxc − byc is not valid for all real numbers
x and y.
Solution.
As a counterexample, let x = 0 and y = − 12 . Then
1
bx − yc = b c = 0
2
whereas
1
bxc − byc = −b− c = −(−1) = 1
2
Problem 5.10
Show that the equality dx + ye = dxe + dye is not valid for all real numbers
x and y.
Solution.
As a counterexample, let x = y = 21 . Then
dx + ye = d1e = 1
whereas
dxe + dye = 2
Problem 5.11
Prove that for all real numbers x and all integers m, dx + me = dxe + m.
Solution.
Suppose that x ∈ R and m ∈ Z. Let n = dxe. By definition of ceil function,
n ∈ Z and
n − 1 < x ≤ n.
3
Add m to all sides to obtain
n + m − 1 < x + m ≤ n + m.
Since n + m ∈ Z and n = dxe, we find
dx + me = n + m = dxe + m
Problem 5.12
Show that if n is an odd integer then d n2 e =
n+1
.
2
Solution.
Let n be an odd integer. Then there is an integer k such that n = 2k − 1.
Hence, n2 = k − 12 . By the previous problem
1
1
n+1
n
d e = dk − e = k + d− e = k =
2
2
2
2
4

Download Report