# 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

• 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:

1. Basis: Prove that P(1) is true.
• Actually, we can prove P(i) for any small integer i (eg P(2).

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 ≤ ik. Use this assumption to prove that P(k+1) is true

3. 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
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)
2. Basis: History books indicate that GW was CB so P(1) is true

3. 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
4. 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!

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

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

3. 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.

4. 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.

1. 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)$.
2. 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*}

3. 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)$.

4. 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