Discrete Structures - Tutorial 5
1. Prove that if n is an integer and n3 + 5 is odd, then n must be even.
Sol: (a) We prove the contrapositive. If n is odd, then n3 +5 is even. Assume
that n is odd. Then we can write n = 2k + 1 for some integer k. Then
n3 + 5 = (2k + 1)3 + 5 = 8k 3 + 12k 2 + 6k + 6 = 2(4k 3 + 6k 2 + 3k + 3).
Thus n3 + 5 is two times some integer, so it is even.
(b) Suppose that n3 + 5 is odd and that n is odd. Since n is odd, and
the product of odd numbers is odd, in two steps we see that n3 is odd.
But then subtracting we conclude that 5, being the difference of the
two odd numbers n3 + 5 and n3 is even. This is not true. Therefore
our supposition was wrong and the proof by contradiction is complete.
√
2. Prove that 2 is an irrational number.
√ √
Sol: Let us suppose 2 were a rational number. Then we can write 2 =
a/b where a, b are whole√numbers simplified to the lowest terms, b not
zero. From the equality 2 = a/b it follows that 2 = a2 /b2 , or a2 = 2b2 .
So the square of a is an even number since it is two times something,
and thus a itself must also be an even number. Now, let a = 2k. If
we substitute a = 2k into the original equation 2 = a2 /b2 , we get:
2 = (2k)2 /b2 , i.e., b2 = 2k 2 . This means b2 is even, from which it
follows again that b itself is an even number. Our assumption was a/b
is simplified to the lowest terms, and now √ it turns out that a and b
would both be even — (contradiction). So, 2 cannot be rational.
3. Use induction to prove the following generalization of one of De Mor-
gan’s laws:
n
\ n
[
Aj = Aj
j=1 j=1
whenever A1 , A2 , . . . , An are subsets of a universal set U and n ≥ 2.
1
Sol: Let P (n) be the identity for n sets.
Basis step: The statement P (2) asserts that A1 ∩ A2 = A1 ∪ A2 (Proof
already covered in class).
Inductive step: The inductive hypothesis is: let P (k), k ≥ 2 be true,
i.e.,
k
\ k
[
Aj = Aj
j=1 j=1
holds whenever A1 , A2 , . . . , An are subsets of a universal set U. Now
we need to show that P (k + 1) must also hold.
k+1 k
!
\ \
Aj = Aj ∩ Ak+1
j=1 j=1
(by the definition of intersection)
k
!
\
= Aj ∪ Ak+1
j=1
(by DeMorgan’s law where the two sets are kj=1 Aj and Ak+1 )
T
k
!
[
= Aj ∪ Ak+1
j=1
(by the inductive hypothesis)
k+1
[
= Aj
j=1
(by the definition of union)
This completes the inductive step.
4. An odd number of people stand in a yard at mutually distinct distances.
At the same time each person throws a pie at his nearest neighbour,
hitting this person. Use induction to show that there is at least one
person who is not hit by a pie.
Can the same be said if there are even number of people?
Sol: Let P (n) denote the statement ‘there is a survivor (who is not hit) in
the odd pie fight with 2n + 1 people’.
Basis step: P (1), there are 3 people. Of the three people, suppose that
2
the closest pair is A and B, and C is the third person. Since distances
between people are different, the distances between A and C, and B
and C are greater than that between A and B. Therefore, A and B
throws pies at each other, and C survives.
Inductive step: Suppose that P (k) is true, that is, in the pie fight with
2k + 1 people there is a survivor. Consider the fight with 2(k + 1) + 1
people. Let A and B be the closest pair of people in this group of
2k + 3 people. Then they throw pies at each other. If someone else
throws a pie at one of them, then for the remaining 2k + 1 people there
are only 2k pies, and one of them survives. Otherwise the remaining
2k + 1 people throw pies at each other, playing the pie fight with 2k + 1
people. By the inductive hypothesis, there is a survivor in such a fight.
For an even number of people there may not be any such survivor.
n n
!2
X X
5. Prove by induction k3 = k
k=1 k=1
n n
!2
Xn(n + 1) X n2 (n+1)2
Sol: We know k = . Therefore, k = 4
. So, we
k=1
2 k=1
2 2
basically need to prove that 13 + 23 + 33 + · · · + n3 = n (n+1)4
.
Basis step: n = 1, the basis step obviously holds since both LHS and
RHS evaluate to 1.
2 2
Inductive step: Let for n = k, 13 +23 +33 +· · ·+k 3 = k (k+1)4
(inductive
hypothesis). Now we need to show that the claim holds for n = k + 1.
k+1
X 2 2
Thus, j 3 = 13 + 23 + 33 + · · · + k 3 + (k + 1)3 = k (k+1)
4
+ (k + 1)3
j=1
k 2 (k+1)2 +4(k+1)3
= 4
(k+1)2 (k 2 +4(k+1))
= 4
(k+1)2 (k 2 +4k+4)
= 4
(k+1)2 (k+2)2
= 4
k+1
!2
X
= j .
j=1
6. Explain what is wrong with the reasoning of the following proof. Re-
member that saying the claim is false is not a justification.
For all x, y, n in {0, 1, 2, . . .}, if max(x, y) = n, then x = y.
Proof (by induction):
Base case: Suppose that n = 0. If max(x, y) = 0 and x, y are in
3
{0, 1, 2, . . .}, then x = y = 0.
Induction step: Assume that whenever we have max(x, y) = k, then
x = y must follow. Next, suppose x, y are such that max(x, y) = k + 1.
Then it follows that max(x − 1, y − 1) = k, so by the inductive hypoth-
esis, x − 1 = y − 1 ⇒ x = y, completing the induction step.
Sol: If x and y are in N = {0, 1, 2, . . .} it is not necessarily true that x − 1
and y − 1 are in N. If you want to show max(0, 1) = 1 implies 0 = 1,
you are looking at max(−1, 0) = 0. That isn’t covered in the k = 0
case.