Massachusetts Institute of Technology Handout 9 6.042J/18.062J: Mathematics for Computer Science September 15, 2000 Professors Nancy Lynch and Shlomi Dolev

Tutorial 2 Problems

Problem 1

(a) Show that (∀xP (x)) ∨ (∀xQ(x)) is not logically equivalent to ∀x(P (x) ∨ Q(x)) (that is, that the universal quantifier does not distribute over OR).

Solution: Even if ∀x(P (x)∨Q(x)), there may be two elements, c_{1} and c_{2}, such that P (c_{1})∧ ¬Q(c_{1}) ∧ ¬P (c_{2}) ∧ Q(c_{2}), and thus, ¬(∀xP (x) ∨ ∀xQ(x)).

For example, suppose the universe of discourse is ℕ, P (x) is the proposition “x is even,” and Q(x) is the proposition “x is odd.” It is not true that every natural number is even (i.e., ¬∀xP (x)), nor is it true that every natural number is odd (i.e., ¬∀xQ(x)). However, every natural number is either even or odd (i.e., ∀x(P (x) ∨ Q(x))).

(b) Show that the existential qualifier does distribute over OR.

Solution: This problem asks us to prove ∃x(P (x) ∨ Q(x)) ⟺ ∃xP (x) ∨ ∃xQ(x).

Proof: Suppose that ∃x(P (x) ∨ Q(x)). By existential instantiation, for some c ∈ U, P (c) ∨ Q(c). By existential generalization, ∃xP (x) ∨ ∃xQ(x).

To see the other direction, suppose ∃xP (x) ∨ ∃xQ(x). We proceed by cases:

Case 1 (∃xP (x)): By existential instantiation, P (c) for some c ∈ U. Therefore P (c)∨Q(c), and by existential generalization, ∃x(P (x) ∨ Q(x)).

Case 2 (∃xQ(x)): This is exactly analogous to the previous case.

Exhaustive cases: Since we have covered both disjuncts of our supposition, the two cases above are exhaustive.

Problem 2

(a) A false proof about 2n by 2n tilings.

Claim. For n ∈ ℕ, n ≥ 1, any 2n × 2n square grid can be tiled by L-shaped tiles such that any particular square is left untiled.

Proof. The proof is by strong induction on n. Let P (n) be the predicate: “Any 2n × 2n square grid can be tiled by L-shaped tiles such that any particular square is left untiled”.

Base Case:

The base case, for n = 1, is very simple: just use one tile.

Inductive Step:

Assume that the claim is true for all square grids smaller than 2n, and we prove it for the 2n × 2n square grid. This follows the proof of the 2^{n} × 2^{n} case: Given a 2n × 2n square grid, with one square designated to be left untiled, we construct a tiling (using L-shaped tiles) for all the other squares, as follows: Divide the square grid up into four quadrants, each n × n. By the inductive hypothesis (since n < 2n for all n ≥ 1), we can tile each of these quadrants (with the L-shaped tiles) completely, except for one square of our choice. For the quadrant with the square to be left untiled, choose that square. For the others, choose the squares at the corner where the quadrants meet. This forms an L-shaped space at the center of the 2n × 2n square grid, which can be filled by a single L-shaped tile. Thus, the entire 2n × 2n square grid is tiled, except for the square designated.

Point out any logical errors in this proof (that is, not simply places where some steps were skipped, but where there is actually an error, though you are free to point out places where more steps should have been included for clarity). Then, either construct a correct proof, or show that the claim is false.

Solution: The error in the proof is that we erroneously invoke the induction hypothesis. The inductive hypothesis states that we can tile all square grids of size 2m × 2m, for all m ∈ ℕ, m < n. That is, we can tile all square grids of even size that are smaller than the 2n × 2n square grid. When we invoke the induction hypothesis, we use it to claim that we can tile an n × n square grid. The problem occurs when n is odd.

In fact, the claim is false. Consider n = 3, i.e., a 6 × 6 square grid. The grid contains 36 squares which is divisible by 3 the number of squares of an L-shaped tile. Thus, it is not possible to tile such a grid so that exactly one particular square is left untiled.

(b) Show that a 7 by 7 chessboard with one square removed can be completely covered using L-shaped tiles.

(c) Show that an n by n chessboard with one square removed can be completely covered using L-shaped pieces of the sort described in lecture, if n > 5, n is odd, and n is not divisible by 3.

Problem 3 (a) Prove that 2^{0} + 2^{1} + ⋯ + 2^{n} = 2^{n+1} − 1, for every n ∈ N.

Solution: The proof is by induction: Inductive Hypothesis P(n): 2^{0} + 2^{1} + ⋯ + 2^{n} = 2^{n+1} − 1 Base Case: n=0. 2^{0} = 2^{1} − 1. So the base case works. Inductive Step: Assume P(n) in order to show P(n+1) is true. P(n+1) says that 2^{0} + 2^{1} + ⋯ + 2^{n} + 2^{n+1} = 2^{n+2} − 1. From our inductive hypothesis, we know that the first n + 1 terms of the above equation sum up to 2^{n+1} − 1, so let’s substitute that in to P(n+1):

2^{n+1} − 1 + 2^{n+1} = 2 ∗ (2^{n+1} − 1)
= 2^{n+2} − 1

p(n+1): 2^{n+2} − 1 = 2^{n+2} − 1. We have used P(n) to show that P(n+1) is true, so the proof is complete.

(b) Come up with a formula for 3^{0} + 3^{1} + ⋯ + 3^{n}, and prove your formula.

Solution: The formula is \frac{3^{n+1}−1}{2}. The proof by induction is nearly identical to the one above.