Chapter 4 - Direct Proof

4.1 Theorems

4.2 Definitions

4.3 Direct Proof

4.4 Using cases

4.5 Treating Similar Cases

See extra credit discussion in Canvas.

Chapter 5 - Contrapositive Proof

Recall, the conditioanl $P \Rightarrow Q$ is logically equivalent to the contrapositive $\lnot Q \Rightarrow \lnot P$. Sometimes it is much easier to proof the contrapostivie than the conditional.

5.1 Contrapositive Proof

Question 1: Proof the following propositions using direct proof. Then prove the same statement using the contrapositive.

Proposition A: Suppose $x \in \mathbb{Z}$. If $7x+9$ is even, then $x$ is odd.

Proposition B: Suppose $x \in \mathbb{Z}$. If $x^2-6x+5$ is even, then $x$ is odd.

5.2 Congruency of Integers

Let $a,b \in \mathbb{Z}$ and $n\in\mathbb{N}$. We say that $a$ and $b$ are $congruent modulo n$ if $n$ divides $(a-b)$ (written $n|(a-b)$). This is written as

\[a \equiv b (\text{mod } n)\] If $a$ and $b$ are not congruent modulo $n$, we write: \[a \not\equiv b (\text{mod } n)\]

Example: $6 \equiv 10 (\text{mod } 4)$ because 4 divides (6-10).

Example: $7 \not\equiv 10 (\text{mod } 4)$ because 4 does not divide (7-10).

Question 1: Let X be the set of all numbers that are congruent to 1 modulo 4. Find X.

Question 2: Prove the following proposition using direct proof.

Let $a,b \in \mathbb{Z}$ and $n\in\mathbb{N}$. If $a \equiv b (\text{mod } n)$, then $a^2 \equiv b^2 (\text{mod } n)$.

Question 3: Prove the following propositions using contrapositive proof.

Let $a,b \in \mathbb{Z}$ and $n\in\mathbb{N}$. If $12a \equiv 12b (\text{mod } n)$, then $n$ does not divide 12.

5.3 Mathematical Writing

Question 1: Read Section 5.3 and write/summarize the 12 guidelines for mathematical writing.

Question 2: From the textbook exercises, do A2-6,12 and B14-22. Make sure you apply the 12 guidelines in writing your proofs.

Chapter 6 - Proof by Contradition

6.1 Proving Statements with Contradiction

6.2 Proving Conditional Statements by Contradiction

Do the exercises at the end of chapter 6: #1-3,5-6,8-10,16-18.

6.3 and 6.4 Choosing Proof Strategies

See extra credit discussion in Canvas.

Chapter 7 - Proving Non-Conditional Statements

Chapter 8 - Proof Involving Sets

Chapter 9 - Disproof

Chapter 10 - Mathematical Induction

10.1 Proof by Induction

Question 1: From the textbook exercises at the end of Chapter 10, do #1-3.

10.2 Proof by Strong Induction

Question 1: For more practice, do #4-6 from the exercises at the end of Chapter 10.

Sometimes using proof by induction is a bit easier if we make a stronger assumption at the inductive step. Instead of showing $S_k \Rightarrow S_{k+1}$, we could get to the same conclusion by showing $(S_1 \land S_2 \land ... \land S_k) \Rightarrow S_{k+1}$. This technique is called strong induction:

Proposition: Statements $S_1, S_2, S_3, … $ are all true.
Proof: (Strong induction)
(1) Show that $S_1$ is true. (Or the first several S_n if this helps.) (2) Given any integer $k \geq 1$, prove $(S_1 \land S_2 \land ... \land S_k) \Rightarrow S_{k+1}$.

Question 1: Use strong induction to prove the following:
Any postage stamp of 8 cents or more is possible to make using 3 and 5 cent stamps.

Question 2: Use strong induction to prove the following: If $n \in \mathbb{n}$, then $12 | (n^4 - n^2)$.

A graph is a configuration of points (vertices) and line (edges). A graph has a cycle if it has way you can travel along edges from one point back to itself.

Question 3: Draw a graph with a cycle.

A graph is called a tree if it has no cycles.

Question 4: Draw your graph from Question 3, but with enough removed edges to make it a tree!

Question 5: Use strong induction to prove that:
If a tree has $n$ vertices, then it has $n-1$

10.3 Proof by Smallest Counterexample

Another proof technique, proof by smallest counter example, is a hybrid of induction and proof by contradiction. Here is the outline:

Proposition: Statements $S_1, S_2, S_3, … $ are all true.
Proof: (Smallest counterexample)
(1) Show that $S_1$ is true.
(2) For the sake of contradiction, suppose that not every $S_n$ is true.
(2) Let $k>1$ be the smallest integer for which $S_k$ is false.
(4) Then $S_{k-1}$ must be true. Use this to derive a contradiction.

Question 1: Use proof by smallest counterexample to prove:
If $n \in \mathbb{Z}$, then $4 | (5^n-1)$.

10.3 Fundamental Theorem of Arithmetic

Question 1: Use induction to prove the Fundamental Theorem of Arithmetic:

Any integer $n>1$ has a unique prime factorization.

10.4 Fibonacci Numbers

Question 1: Use Google to find out: what is the Fibonacci sequence. How does it relate to the Golden Ratio?

Question 2: Use induction to prove that the Fibonacci sequence obeys: \[F^2_{n+1} - F_{n+1}F_n - F^2_n = (-1)^n\]

MATH 3253 - Foundation of Mathematics

Course Notes - Fall 2021

Paul Regier