Chapter 0 - Proofs

Terminology

Definition: precise description of the objects and notions that we use

Mathematical statement: precise statement about the objects and notions that we use, typically that it has some property

Is either true or false

Proof: convincing argument that a statement is true

Theorem: Statement that has been proved to be true

Lemma: True statement used to prove a Theorem

Corollary: True statement that follows easily from a Theorem

Hints for Finding Proofs

No magic formula

Understand statement:

Write in own words
Consider parts separately

Recognize hidden parts:

iff
To prove that 2 sets are equal (ie A = B), prove that A ⊆ B and B ⊆ A

Think about why the statement must be true

Consider examples:

Try examples that have the property
Try to find examples that don't have the property

Attempt something easier (eg special case)

Write up ideas clearly

Come back to it; be patient

Types of Proof: Proof by Construction

To prove that an object exists, show how it can be constructed

Example: A 3-regular graph of degree n exists for every even number n

Types of Proof: Proof by Contradiction

To prove P, assume ~P and use it to prove a contradiction (ie to another statement that is obviously false). Then conclude that P must be true.

Example from the text, revised: Use the "fact" that if it's raining, then everyone who comes in from the outside has an umbrella to prove it's not raining. First, assume that it is raining. Therefore, from the "fact" given above, everyone who comes in will have an umbrella. Someone just came in from outside without an umbrella. This is a contradiction. Thus we conclude that it is not raining.

The method of this proof is valid, but the conclusion is only valid if the "fact" really is a fact!

Example from the net: Prove p: that there is no smallest positive rational number. First assume p is false, that is, that there is a smallest positive rational. Call the smallest rational number r...

Example from the text: square root of 2 is irrational

Careful: When using proof by contradiction, mistakes can lead to apparent contradictions.

For homework: Prove there is no largest prime number. Please work on this yourself and don't look up a solution.

Types of Proof: Proof by Induction

Inductive proofs of P(n) for all n ≥ 1 follow this format:

Basis: Prove that P(1) is true.

Actually, we can prove P(i) for any small integer i (eg P(2).

Induction step: assume P(k-1) is true and use this assumption to prove P(k) is true (ie prove that the property jumps from one integer to the next).

Alternatively, assume P(k) is true and use this assumption to prove P(k+1).
Alternatively, Assume that P(i) is true for 1 ≤ i ≤ k. Use this assumption to prove that P(k+1) is true

From 1 and 2, conclude that P(n) is true for all n ≥ 1.

Example 1: Prove P(n)that the descendents of George Washington (GW) at generation n are colorblind (CB) for every n ≥ 1

Use this "fact": Colorblindness is hereditary: children of a colorblind parent are themselves colorblind.

In other words, if P(k) then P(k+1)

Basis: History books indicate that GW was CB so P(1) is true

Induction step: Assume, for arbitrary k ≥ 1, p(k): that generation k is colorblind. Thus, from the "fact" given above, we have P(k+1): generation k+1 is colorblind
Hence all generations are colorblind.

Example 2: Prove that the sum of 1 to n is n(n+1)/2 for all n ≥ 1

See expanded proof below!

For any n ≥ 1, let P(n) represent the proposition that the sum of 1 to n is n(n+1)/2.

Basis: P(1) is true since the sum of 1 to 1 is 1(1+1)/2.

Induction step: Assume that P(k) is true, meaning that we assume that the sum of 1 to k is k(k+1)/2. Now consider the sum of 1 to (k+1) which equals ... Thus, P(k+1) is true.

Thus we conclude that P(n) is true for all n ≥ 1.

Proof by Induction: Example

Let $P(n)$ be the statement $\displaystyle \sum_{i=1}^n i = \frac{n(n+1)}{2}$.

Prove P(n) ∀ n ≥ 1. Use proof by induction. Prove $P(n) \forall n \ge 1$. Use proof by induction.

Basis: Prove $P(1)$, that is, that $\displaystyle \sum_{i=1}^1 i = \frac{1(1+1)}{2}$. But $\displaystyle \sum_{i=1}^1 i = 1$ and $\frac{1(1+1)}{2} = 1$, and this proves $P(1)$.
Inductive Step: Assume $P(k)$ for an arbitrary k ≥ 1. This is the Inductive Hypothesis. Now we must show that $P(k)$ implies $P(k+1)$, that is, that $\displaystyle \sum_{i=1}^{k} i = \frac{(k)(k+1)}{2}$ implies that $\displaystyle \sum_{i=1}^{k+1} i = \frac{(k+1)(k+1+1)}{2}$. (In other words, P(k) ⇒ P(k+1)).

$ \displaystyle \begin{align*} \text{Now } \sum_{i=1}^{k+1} i & = \sum_{i=1}^{k} i + (k+1), \text{by definition of summation} \\ & = \frac{k(k+1)}{2} + (k+1), \text{by the Inductive Hypothesis} \\ & = \frac{k^2+k+2k+2}{2} \\ & = \frac{k^2+3k+1}{2} \\ & = \frac{(k+1)(k+2)}{2} \\ & = \frac{(k+1)(k+1+1)}{2} \end{align*} $

Thus, we have proved that $\displaystyle \sum_{i=1}^{k+1} i = \frac{(k+1)(k+1+1)}{2}$, which is $P(k+1)$. Thus, from $P(k)$ we have proved $P(k+1)$.

Therefore, from 1 and 2 we conclude by induction that P(n) is true for all n ≥ 1

How did we do this?

Start from what we know.
Be aware of where we're trying to go.
Use definitions.

ITEC 420 Course Page