Massachusetts Institute of Technology Lecture 2 6.042J/18.062J: Mathematics for Computer Science September 12, 2000 Professors Nancy Lynch and Shlomi Dolev

Predicate Reasoning; Proof by Induction

Topics for today:

• Predicates

• Predicate reasoning examples

• (Ordinary) mathematical induction

• Inductive proof examples

Reading: Velleman Chapter 2; Sections 3.3, 6.1, 6.2; Rosen 1.3, 3.1, 3.2, 3.3

1 Predicates

1.1 What are predicates?

Predicates are similar to propositions but they depend on variables. P (x, y, z) denotes a predicate on variables x, y, z. Examples:

• P (x): x is a prime number.

• Q(x): x > 2.

• R(x): x is an odd number.

These predicates are not propositions, because they can be true or false depending on the value of the variable x. When the value of x is not specified, we say x is unbound. Predicates are like functions from the domains of the variables to propositions.

• P (2) is true.

• R(2) is false.

• P (4) ∨ R(3) is true.

• Q(3) ∧ R(4) is false.

• Q(1) ⟹ R(2) is true.

1.2 Quantifiers

Many propositions assert that something is true for all or some elements of a given domain (e.g., all natural numbers). The following quantifiers presume a particular universe of discourse has been agreed upon in advance. This is the set of elements which can be assigned to the quantified variables.

“∀” means “for all.” ∀xP (x) is a statement that is true iff P (x) is true for every x in the universe of discourse.

“∃” means “there exists.” ∃xP (x) is true iff P (x) is true for at least one x in the universe of discourse.

“∄” mean “there does not exist” (“there is no”).

“∃!” means “there exists exactly one.”

“∀x ∈ S” means “for every x in the set S.” (∀x ∈ S)P (x) is equivalent to ∀x(x ∈ S ⟹ P (x)).

Quantifiers can turn predicates into propositions. For example:

∀x(P (x) ∧ Q(x) ⟹ R(x))

Each occurrence of x is associated with the ∀ quantifier. A variable occurrence associated with a quantifier in this way is said to be bound. Since every variable in the expression above is bound, it is a proposition. If P, Q, and R are the predicates defined above, this proposition says “every prime number greater than 2 is odd” and is true.

Note: ∀x∃y is different from ∃y∀x:

• Suppose S(x, y) means student x falls asleep in class y.

• ∀y∃xP (x, y) : “In every class, some student falls asleep.”

• ∃x∀yP (x, y) : “There exists a student who falls asleep in every class.”

1.3 Deduction rules involving quantifiers

We’ve already seen deduction rules for arbitrary propositions. There are others special to propositions with quantifiers. First, for negating quantified statements:

• ¬[∀xS(x)] is equivalent to ∃x¬S(x).

Example: ∀xS(x) : For all primes x > 2, x is odd.

∃x¬S(x) : There is some prime x > 2 such that x is not odd.

(Domain of discourse: The set of primes > 2)

• ¬[∃xS(x)] is equivalent to ∀x¬S(x).

Example: ∃xS(x) : There is an even prime.

∀x¬S(x) : All primes are not even. (Domain of discourse: Primes)

There are four main rules for manipulating quantifiers in proofs:

Universal Generalization UG: To prove something is true for all x (∀x), we can show that it works for an arbitrary fixed x.

Universal Instantiation UI: If a statement is true for all x (∀x), then it is true for any particular x we want to study.

Existential Generalization EG: If we have exhibited one x that satisfies some property, we have proved one exists (∃x).

Existential Instantiation EI: If we know that some x exists satisfying a property (∃x), then we can choose one and use it in the proof.

Like axioms, these inference rules are agreements to believe certain inferences. For example, the constructivists (e.g. Brouwer) reject the claim that ¬[∀xP (x)] implies ∃xP (x). They claim that to prove something exists, you actually have to construct it. Brouwer retracted his most famous theorem after he became a constructivist, since the proof was nonconstructive.

2 Predicate reasoning examples

We revisit some of the examples from last time, pointing out uses of quantifier reasoning.

2.1 Birthdate

Last time we did a proof by cases that d^{2} + d is even for any birthdate d. We can generalize this so it talks about all natural numbers, not just 1-31.

Prove: ∀n ∈ N(n^{2} + n is even).

1. Fix n ∈ N.

2. n^{2} + n is even. ???

3. QED Universal Generalization (UG)

UG says, to show something is true for all elements of a set (∀), you pick (“fix”) any arbitrary generic element and show it for that. The general pattern for using UG is:

Prove: ∀x ∈ X(P (x)).

1. Fix x ∈ X.

2. P (x)

3. QED Universal Generalization (UG)

Now back to the proof. To show step 2, we can use cases:

Prove: ∀n ∈ N(n^{2} + n is even).

1. Fix n ∈ N.

2. n^{2} + n is even.

1. If n is odd then n^{2} + n is even. ???

2. If n is even then n^{2} + n is even. ???

3. QED Cases 3. QED Now fill in steps for the even case. This assumes a definition of “even” for a natural number, which says that the number is expressible as 2x for some natural number x.

2. If n is even then n^{2} + n is even. 1. Assume n is even.

2. n^{2} + n is even.

1. ∃x ∈ N(n = 2x) Definition of “even”

2. Choose x ∈ N, n = 2x Existential Instantiation (EI) (If there exists one, you can choose one.)

3. n^{2} + n = 4x^{2} + 2x = 2(2x^{2} + x) Algebra

4. ∃y ∈ N(n^{2} + n = 2y) Existential Generalization (EG) (If you have one, then one exists.)

5. QED Definition of “even”

3. QED Implication

Or, condensing a little:

2. If n is even then n^{2} + n is even. 1. Assume n is even.

2. Choose x ∈ N, n = 2x Definition of “even”, EI

3. n^{2} + n = 4x^{2} + 2x = 2(2x^{2} + x) Algebra

4. n^{2} + n is even. EG, definition of “even”

5. QED Implication

Analogously for the odd case (using a definition of “odd” that says that the number is expressible in the form 2x + 1):

1. If n is odd then n^{2} + n is even. 1. Assume n is odd.

2. n^{2} + n is even.

1. ∃x ∈ N(n = 2x + 1) Definition of “odd”

2. Choose x ∈ N, n = 2x + 1 EI

3. n^{2} + n = 4x^{2} + 4x + 1 + 2x + 1 = 2(2x^{2} + 3x + 1)

Algebra

4. ∃y ∈ N(n^{2} + n = 2y) EG

5. QED Definition of “even”

3. QED Implication

2.2 \sqrt{2} is irrational

Here is the proof from last time, with uses of quantifier reasoning mentioned explicitly.

Prove: \sqrt{2} is irrational.

1. \sqrt{2} rational ⇒ false 1. Assume \sqrt{2} rational.

2. false 1. Choose a, b ∈ N^{+}, \sqrt{2} = \frac{a}{b}, lowest terms. Basic properties of rationals, EI 2. 2b^{2} = a^{2} Algebra

3. a^{2} is even. EG, definition of “even”

4. a is even. ???

5. Choose c ∈ N, a = 2c. Definition of “even”, EI

6. 4c^{2} = a^{2} = 2b^{2} Algebra

7. 2c^{2} = b^{2} Algebra

8. b^{2} is even. EG, definition of “even”

9. b is even. ???

10. a and b aren’t in lowest terms. 1.2.4, 1.2.9

11. QED 1.2.1, 1.2.10, propositional logic 3. QED Implication

2. QED Contradiction

Missing piece: Showing that a and b are even, because their squares are even. Prove this by contradiction, e.g.:

4. a is even.

1. a is odd ⇒ false 1. Assume a is odd.

2. a^{2} is odd. Do a proof like the one in the birthdate example, using EI, algebra, and EG.

3. false 1.2.3, 1.2.4.1.2, Propositional logic

2. QED Contradiction

Actually, since we are using the same argument twice, it’s better style to extract and reuse some general lemmas. (In these, we’re using x_{0} for the values that we fix, to try to avoid some of the confusion between the different uses of x.)

Lemma 1: Prove: ∀x ∈ N[x odd ⟹ x^{2} odd].

1. Fix x_{0} ∈ N.

2. x_{0} odd ⟹ x_{0}^{2} odd.

1. Assume x_{0} is odd.

2. Choose y ∈ N, x_{0} = 2y + 1. Definition of “odd”, EI 3. x_{0}^{2} = 4y^{2} + 4y + 1 = 2(2y^{2} + 2y) + 1 Algebra

4. x_{0}^{2} is odd. EG, definition of “odd”.

5. QED Implication

3. QED UG

Lemma 2: Prove: ∀x ∈ N[x^{2} even ⟹ x even].

1. Fix x_{0} ∈ N.

2. x_{0}^{2} even ⟹ x_{0} even.

1. Assume x_{0}^{2} even

2. x_{0} odd ⟹ x_{0}^{2} odd. Lemma 1, UI

3. x_{0} even. Propositional reasoning 4. QED Implication

3. QED UG Once we have Lemma 2, we can apply it in the main proof to a and b (again using UI).

Compare the structured proof that \sqrt{2} is irrational with a typical paragraph proof. The paragraph proof follows the same strategy, but leaves you to figure out the structure and more of the reasons.

Proof. The proof is by contradiction. Assume for purpose of contradiction that \sqrt{2} is rational. Then we can write \sqrt{2} = a/b where a and b are integers and the fraction is in lowest terms. Squaring both sides gives 2 = a^{2}/b^{2} and so 2b^{2} = a^{2}. This implies that a is even; that is, a is a multiple of 2. As a result, a^{2} is a multiple of 4. Because of the equality 2b^{2} = a^{2}, 2b^{2} must also be a multiple of 4. This implies that b^{2} is even and so b must be even. But since a and b are both even, the fraction a/b is not in lowest terms. This is a contradiction, and so the assumption that \sqrt{2} is rational must be false.

2.3 De Morgan’s Law

Prove: ∀A, B(\overline{A} ∩ \overline{B} = \overline{A ∪ B})

1. Fix A, B.

2. \overline{A} ∩ \overline{B} = \overline{A ∪ B} ???

3. QED UG

To show two sets are equal, we show that they contain the same elements (a standard method):

Prove: ∀A, B(\overline{A} ∩ \overline{B} = \overline{A ∪ B}).

1. Fix A, B.

2. \overline{A} ∩ \overline{B} = \overline{A ∪ B}

1. ∀x(x ∈ \overline{A} ∩ \overline{B} ⇔ x ∈ \overline{A ∪ B})

1. Fix x.

2. x ∈ \overline{A} ∩ \overline{B} ⇔ x ∈ \overline{A ∪ B} ???

3. QED UG 2. QED Definition of set equality.

3. QED UG

Equivalence can be shown by showing two implications, one in each direction:

2. x ∈ \overline{A} ∩ \overline{B} ⇔ x ∈ \overline{A ∪ B}

1. x ∈ \overline{A} ∩ \overline{B} ⇒ x ∈ \overline{A ∪ B} ???

2. x ∈ \overline{A ∪ B} ⇒ x ∈ \overline{A} ∩ \overline{B} ???

3. QED Propositional logic

We already showed the first direction in last lecture. The other direction reverses the steps:

2. x ∈ \overline{A ∪ B} ⇒ x ∈ \overline{A} ∩ \overline{B}

1. Assume x ∈ \overline{A ∪ B}.

2. x ∉ A ∪ B Definition of complement 3. x ∉ A, x ∉ B Definition of union

4. x ∈ \overline{A}, x ∈ \overline{B} Definition of complement 5. x ∈ \overline{A} ∩ \overline{B} Definition of intersection 6. QED Implication

Actually, the union step could be expanded to a little proof by contradiction: if x is in one of the sets, then it’s in the union.

2.4 Counterexamples

Counterexamples are the easiest way to avoid proving a theorem, e.g.: Prove: All natural numbers ≥ 2 are prime.

This is false. We can show this using a “counterexample”, 10. That’s all that’s needed. Really, we’re proving the negation, which says ∃ a non-prime ≥ 2. And this follows just by exhibiting one (Existential Generalization).

3 General Remarks about Proofs

3.1 What we expect in your proofs

In practice, people do not write out real proofs about interesting mathematical objects in a completely formal, step-by-step style (unless they are using a computer-aided theorem prover). Rather, they give a kind of proof sketch, skipping some steps. That is what we expect you to do in your proofs on problem sets and tests.

However, in writing out your proof sketches, it is very important to work correctly, so that all the missing steps could be filled in. As in a scientific experiment, it should be possible for someone else to “replicate” (i.e., understand, fill in the details of) your proof. In your homework, that “someone” should be another 6.042 student.

In the real world, anything that has already been proved somewhere can be cited and used without proof. But in this course, you can’t do this (because just about everything we ask you to prove has already been proved somewhere). General guidelines: We don’t expect you to reprove arithmetic. Anything from high school math can be used without proof (unless stated otherwise). Once something has been proved in this course, you can use it again without proof, citing the theorem. Once it has been used so often as to become commonplace, you can even stop citing the theorem.

Do not introduce any new axioms or rules of deduction!

When in doubt about whether something can be stated without proof, prove it!

3.2 Wrong proofs

In this course (and later on), you will encounter incorrect proofs. It is good to learn how to find the bugs. If a proof is written carefully, the problem is usually obvious; it’s trickier when proofs are sketchy or sloppy. Some things that can go wrong:

• Deriving a new statement by an invalid deduction rule, such as A ⟹ B, and B, therefore A.

• Unstated axiom. Gauss once said “Clearly if a curve enters a region, it has to leave.” This was accepted as a reason in a proof for a long time; only a century later was it cleared up.

• Misusing a definition. Using something “obvious” in the intent of the definition that doesn’t actually arise from the formal definition.

The most common problem is a gap between intuition and formalism.

3.3 Wrong proofs through the ages...

If you make mistakes, you are in good company. Even great mathematicians can goof proofs.

• Andrew Wiles recently announced a proof of Fermat’s Last Theorem. It was several hundred pages long. It took mathematicians months of hard work to discover it had a fatal flaw (so Wiles produced another proof of several hundred pages; this one seems to have convinced people for now).

• Kempe’s invalid “proof” of the Four Color Theorem stood for 10 years (1879–1890)

• Gauss’s 1799 Ph.D. thesis is usually referred to as being the first rigorous proof of the Fundamental Theorem of Algebra (every polynomial has a zero over the complex numbers). But it contains quotes like

“If a branch of an algebraic curve enters a bounded region, it must necessarily leave it again. ... Nobody, to my knowledge, has ever doubted [this fact]. But if anybody desires it, then on another occasion I intend to give a demonstration which will leave no doubt.”

Fields Medalist Steve Smale writes about this, calling it an “immense gap” in the proof that was not filled in until 1920, more than a hundred years later.

• In 1900 Poincare carelessly claimed a certain very simple topological characterization of the 3-dimensional sphere. Later realizing it was not so obvious, he demoted the claim to the status of a ”conjecture” in 1904. The Poincare Conjecture is now one of the biggest open questions in mathematics (two Fields Medals have been given out for partial progress on it).

• In the 1940’s Paul Erdos conjectured a certain combinatorial fact about arithmetic progressions (every set of natural numbers of positive density contains arbitrarily long arithmetic progressions), and offered $1000 for a proof or disproof. Endre Szemeredi proved the conjecture in 1972, but the proof was so long and badly written that Erdos was not sure whether to believe it. Finally, Andras Hajnal stepped in and wrote a much clearer version of the same proof, which was eventually published under Szemeredi’s name. At some point during the write-up, Hajnal informed Erdos that he was now confident enough of the proof that he was willing to buy it from Szemeredi for $500.

• There’s also the story of Newton waiting 20 years to publish the Principia because he didn’t see how to prove that one could assume all the mass of a sphere to be concentrated at its center when calculating gravitational attraction. The proof ultimately required the invention of calculus ...

4 Mathematical induction

Induction is the most important proof method in computer science. Suppose you want to prove that P (n) is true for all n ∈ N. 0, 1, 2, . . .. You can prove it individually for 0, 1, . . .. But that has to stop sometime. The proof method of mathematical induction says that you just need to prove it for 0, then prove “if it’s true for n then it’s true for n + 1”.

Why does this prove it for all n ∈ N? It may seem obvious...consider falling dominoes... Actually, it’s part of how N is defined. It’s usually taken as an assumption (axiom) about N:

Induction axiom: [P (0) ∧ ∀n ≥ 0(P (n) ⇒ P (n + 1))] ⇒ ∀n(P (n)). Alternatively, you can see it as a deduction rule. The pattern is:

To prove: ∀n ≥ 0(P (n)) It’s enough to show:

1. (Base) P (0)

2. (Inductive step) ∀n ≥ 0(P (n) ⇒ P (n + 1))

There is a variant if you only want to prove it for n ≥ k:

To prove: ∀n ≥ k(P (n)) It’s enough to show:

1. (Base) P (k)

2. (Inductive step) ∀n ≥ k(P (n) ⇒ P (n + 1))

5 Inductive proof examples

5.1 Sum of Series

This is the canonical first example for induction:

Lemma 5.1 ∀n ≥ 0(1 + 2 + 3 + … + n = \frac{n(n+1)}{2})

Alternatively (and this is better), we can write the LHS in closed form:

∑_{i=1}^{n} i or ∑_{1≤i≤n} i

Thus, we want to prove:

∀n ≥ 0(∑_{i=1}^{n} i = \frac{n(n + 1)}{2})

Let’s stop and be sure we know what this summation means. First check boundary cases (always a good idea to see if you understand a definition).

• If n = 1, then the sum 1 + 2 + 3 + … + n = 1. The sum has one term only. The appearance of 2, 3, and n is misleading!

• If n = 0, then 1 + 2 + 3 + … + n = 0. There are no terms present in the summation.

Now, the induction pattern says:

Prove: ∀n ≥ 0(P (n))

1. (Base) P (0)

2. (Inductive step) ∀n ≥ 0(P (n) ⇒ P (n + 1))

3. QED Induction

Here, we define P (n) to be the predicate ∑_{i=1}^{n} i = \frac{n(n+1)}{2}. In other words:

Prove: ∀n ≥ 0(∑_{i=1}^{n} i = \frac{n(n+1)}{2}).

1. (Base) ∑_{i=1}^{0} i = \frac{0(0+1)}{2}.

2. (Inductive step) ∀n ≥ 0(∑_{i=1}^{n} i = \frac{n(n+1)}{2} ⇒ ∑_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})

3. QED Induction

The two steps of the proof are called the base and the induction step. Usually, the base step is pretty easy to check, but the inductive step can involve some work and creativity.

Whether you give a structured or paragraph style proof, the proof must contain, clearly, all of the following:

1. A statement that the proof is by induction.

2. The definition of the predicate P (n).

3. The proof of the base step, P (0) (or P (k), if we’re starting from some other value k).

4. The proof of the inductive step, ∀n ≥ 0(P (n) ⇒ P (n + 1)

To finish this example: Base: Easy by definition and arithmetic.

1. (Base) ∑_{i=1}^{0} i = \frac{0(0+1)}{2} (P (0))

1. ∑_{i=1}^{0} i = 0 Definition of summation with no terms 2. \frac{0(0+1)}{2} = 0 Arithmetic

3. QED By 1.1 and 1.2.

The inductive step uses basic logic (UG and implication). What’s left is the job of showing that, assuming P (n), we can prove P (n + 1).

2. (Inductive step) ∀n ≥ 0(∑_{i=1}^{n} i = \frac{n(n+1)}{2} ⇒ ∑_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2})

1. Fix n ≥ 0.

2. ∑_{i=1}^{n} i = \frac{n(n+1)}{2} ⇒ ∑_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2} 1. Assume ∑_{i=1}^{n} i = \frac{n(n+1)}{2}

2. ∑_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2} ???

3. QED Implication 3. QED UG

The important job is step 2, showing P (n + 1). To do this, we just write out the equation we want to show (for n + 1), and play around with both sides to try to make them equal. Remember that we are allowed to use the assumption P (n), which is the corresponding equation for n. So while we are manipulating the equation for n + 1, we look for a place to plug in the information for n.

2. ∑_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2}

1. ∑_{i=1}^{n+1} i = (∑_{i=1}^{n} i) + (n + 1) Summation has one extra term.

2. (∑_{i=1}^{n} i) + (n + 1) = \frac{n(n+1)}{2} + n + 1 Inductive hypothesis P (n) (2.2.1)

3. \frac{n(n+1)}{2} + n + 1 = \frac{(n+1)(n+2)}{2} Algebra

4. QED Combining the previous 3 equations.

This worked out nicely because the left hand side (LHS) of the n+1 equation was easily expressible in terms of the n equation. Sometimes we’ll have to work harder. Also, here the choice of P (n) came directly out of the theorem statement. Sometimes it isn’t so obvious.

Also in this example, note that the inductive technique did not help us to come up with the correct expression \frac{n(n+1)}{2} for the summation, but only to prove that it is correct. We’ll see how to come up with such sums when we get to the analysis methods part of this course.

5.2 Divisibility

Definition 5.2 Given two integers x and y, we say x divides y, and write x | y, if there is no remainder on division of y by x. That is, y = cx for some integer c.

Lemma 5.3 ∀n ∈ N, n ≥ 0(6|n^{3} − n)

We will prove this by induction on n, with base case 0. Thus, P (n) is the predicate 6|n^{3} − n. Base P (0) looks obvious, because 6|0 by definition. How about the inductive step?

Prove: ∀n ∈ N, n ≥ 0(6|n^{3} − n)

1. (Base) 6|0^{3} − 0

2. (Inductive step) ∀n ≥ 0(6|n^{3} − n ⇒ 6|(n + 1)^{3} − (n + 1))

1. Fix n ≥ 0.

2. Assume 6|n^{3} − n

3. 6|(n + 1)^{3} − (n + 1) ???

4. QED Implication, UG (condensing two steps)

3. QED Induction

Now, how to get from 2.2 to 2.3? Since both the expressions have high-order n^{3} terms, we can try subtracting. The difference is ((n + 1)^{3} − (n + 1)) − (n^{3} − n), which works out to 3n^{2} + 3n. If we know that 6 divides this difference, and we are assuming that 6 divides n^{3} − n, it follows that 6|(n + 1)^{3} − (n + 1), which is the sum. That’s what we needed.

So the problem reduces to showing 6|3n^{2} + 3n. This factors into 3(n^{2} + n). But we know that n^{2} + n is even, that is, 2|n^{2} + n. If we multiply the expression by 3, then 6 certainly divides the result.

This discussion contained all the ideas needed for the proof. Now we will put it all together in a complete proof.

Prove: ∀n ∈ N, n ≥ 0(6|n^{3} − n)

1. (Base) 6|0^{3} − 0

2. (Inductive step) ∀n ≥ 0(6|n^{3} − n ⇒ 6|(n + 1)^{3} − (n + 1))

1. Fix n ≥ 0.
2. Assume 6|n^{3} − n
3. 6|(n + 1)^{3} − (n + 1)

1. (n + 1)^{3} − (n + 1) = n^{3} − n + 3(n^{2} + n) Algebra

2. n^{2} + n is even Proved this earlier today

3. 2|n^{2} + n Definition of |

4. 6|3(n^{2} + n) Multiplying both sides by 3 (basic properties of N)

5. 6|(n^{3} − n) + 3(n^{2} + n) Divides both terms (2.2, 2.3.4), so divides sum.

6. QED 2.3.1, 2.3.5

4. QED

3. QED

The ideas in this proof are given directly, in the order in which they are used. This makes the proof concise and clear. But this is a different order from the way the ideas arose when we came up with the proof in the first place. By switching the order around, we’ve lost information about how we came up with the proof ideas.

In reading proofs, you will see a tension between trying to provide the reader with the cleanest possible final product and providing intuition about how the proof was developed. Neither extreme is perfect—both kinds of information are useful. When you write proofs, you might want to give both the final product and some discussion of how you arrived at it.

5.3 A string example

Lemma 5.4 There are exactly 2^{n} different length n strings of 0s and 1s.

Proof. Let P (n) be the given statement.

Prove: ∀n ≥ 0(P (n))

1. (Base) P (0) There’s exactly one empty string of 0s and 1s.

2. (Inductive step) ∀n ≥ 0(P (n) ⇒ P (n + 1))

1. Fix n ≥ 0.

2. Assume P (n), that is, there are 2^{n} length n strings.

3. P (n + 1), that is, there are 2^{n+1} length n + 1 strings.

Every string of length n can have either a 0 or a 1 attached at the end.

4. QED Implication, UG 3. QED Induction

5.4 Geometry

Definition 5.5 A convex polygon is a polygon such that any straight line between any two vertices doesn’t leave the polygon.

P (n): The sum of the interior angles in any n-sided convex polygon is exactly (n − 2)180 degrees. Prove: ∀n ≥ 3 (The sum of the interior angles in any n-sided convex polygon is exactly (n − 2)180 degrees.)

1. (Base) P (3): Sum of angles in any triangle is 180. Basic fact from geometry

2. (Inductive step) ∀n ≥ 3(P (n) ⇒ P (n + 1))

1. Fix n ≥ 3.

2. Assume sum of angles of any n-sided convex polygon is (n − 2)180.

3. Sum of angles of any n + 1-sided convex polygon is (n − 1)180. 1. Fix any n + 1-vertex convex polygon X, say with vertices x_{1}, x_{2}, …, x_{n+1}.

2. Let Y be the polygon with vertices x_{1}, x_{2}, …, x_{n} (cuts out one vertex).

3. Y is a convex polygon with at least 3 vertices.

4. Sum of interior angles of Y is (n − 2)180. Inductive hypothesis (2.2)

5. Sum of interior angles of triangle T = x_{n}, x_{n+1}, x_{1} is 180.

Basic fact from geometry

6. Sum of angles in X = sum in Y + sum in T, = (n − 2)180 + 180 = (n − 1)180. Basic geometry, arithmetic.

7. QED UG

4. QED Implication, UG

3. QED Induction

UG is used to conclude something about all polygons from what we showed for any particular polygon, and to conclude something about all n from what we showed about any particular n.

5.5 Tiling

Our next proof illustrates some new ideas:

• Sometimes you need to strengthen inductive hypothesis in order to prove it.

• Sometimes induction helps finding a construction, not just do a proof.

The new CS building currently under construction (on Vassar Street, next to the pool) will cost about $140 million. Money has come from many donors, including Bill Gates. Donors get something in return, e.g., something named after them. What Bill G. wants is one of the buildings named after him, plus a statue of himself in the middle of the courtyard.

The planned courtyard consists of 2^{n} × 2^{n} squares, for some n ≥ 1. (We don’t yet know how big n is). The architect, Frank Gehry, wants to cover most of this with L-shaped tiles, each covering three squares. But one of the four center squares will be left empty, for the statue. Can this be done? If so, how? (We want a general solution, for all values of n).

Example: n = 2

Can we prove what we want by induction? For P (n), let’s try: For any 2^{n}×2^{n} courtyard, and any particular central square, ∃ a tiling of the courtyard with exactly that square left untiled.

B

Figure 1: A legal tiling of a 4x4 courtyard. The B marks Bill.

Proof. (doomed attempt) In the base case: n = 1, we can use just one tile. In the inductive step, we try to produce a tiling of a 2^{n+1} × 2^{n+1} courtyard with one center square blank. We can assume tilings of any 2^{n} × 2^{n} courtyard with any center square blank. We might think of subdividing into four 2^{n} × 2^{n} sub-courtyards. But it doesn’t seem to help to be able to tile those with centers left open...

Here we’ve hit the first case where just trying to prove the statement directly by induction doesn’t work. The solution may be surprising: Prove a stronger theorem that implies the one we want. But isn’t that harder? Actually, strengthening a statement to be proved by induction often makes the proof easier. The reason is that, although we have to prove a stronger P (n + 1), we also can rely on a stronger P (n).

Here, let’s redefine P (n) to be the predicate that says, for every square in a 2^{n} × 2^{n} courtyard, we can tile the rest of the courtyard, with that square left blank. Stronger. But now P (n) ⇒ P (n + 1) is easier. And the theorem we wanted originally is just a special case.

Proof. Induction. The base, P (1), is as before. For the inductive step, n ≥ 1, start with an arbitrary 2^{n+1} × 2^{n+1} courtyard with an arbitrary square to leave blank. Let’s try to tile this, assuming tilings of any 2^{n} × 2^{n} courtyard with any square blank.

Again, divide the 2^{n+1} ×2^{n+1} courtyard into four 2^{n} ×2^{n} quadrants. One will contain the square that must be left blank; it can be tiled by inductive hypothesis. Next, put one tile in the center, covering one square in each of the other 3 quadrants. Now use the inductive hypothesis three more times to tile the rest of the 3 quadrants.

Make sure you understand the logical structure of this proof. This proof provides a tiling method, not just existence proof. And it gives a stronger result than we originally were looking for.