Exhaustive Proof

Definition

This is a type of Proof by Cases

Definition

$(p_1\vee p_2\vee \dots \vee p_n)\to q\equiv (p_1\to q)\wedge (p_2\to q)\wedge \dots (p_n\to q)$

the original conditional statement wtih a hypothesis made up of a disjunction of propositions $p_1,p_2,\dots ,p_n$ can be proved by proving each of the $n$ conditional statements $p_i\to q$ individually.

To prove $p\to q$, we can find $p_1\vee p_2\vee \dots \vee p_n\equiv p$ and then individually prove every case.

Link to original

• Some theorems can be proved by examining a small number of examples
• We call this exhaustive proofs
• Better for computers, but even those have limits

Common Errors

Common Errors

• Drawing incorrect conclusions from examples
• No matter how many cases we cover in our own proof, we cannot prove the theorem to be true unless we prove every case

Example: if $x$ is a real number, then $x^2$ is a positive real number.

Proof: Let us consider two cases:

1. $x$ is positive, since a positive number times a positive number is positive, $x^2$ must be positive.
2. $x$ is negative, since a negative number times a negative number is positive, $x^2$ must be positive This “completes” the proof (no it doesn’t. the proof is wrong)

Why? $So{l}^n$: we missed the case where $x=0$

Link to original

Example: It is true that every non-negative integer is the sum of 18 fourth power integers.

$So{l}^n$: To determine if a non-negative integer can $n$ can be written as a sum of 18 fourth powers, we might begin to examine whether $n$ is the sum of 18 fourth power integers for the smallest non-negative integers.

Fourth power integers: $0,1,16,81$.

We can show that non-negative integers add up to ?? can be written as a sum of 18 fourth powers.

One might conclude it is possible based on this example, but 79 cannot be written as a sum of 18 fourth powers.

Example: Prove that $(n+1{)}^3\ge 3^n$ if $n$ is a positive integer such that $n\le 4$

Proof:

$n$ is a positive integer where $n\le 4$. Therefore, $n=1,2,3\text{or}4$

For $n=1$

$$\begin{array}{r}{3}^1\\ \equiv <arithmetic>\\ 3\end{array}$$

And

$$\begin{array}{r}(1+1{)}^3\\ \equiv <arithmetic>\\ 2^3\\ \equiv <arithmetic>\\ 8\end{array}$$

Since, $8\ge 3$, therefore, for $n=1$, $(n+1{)}^3\ge 3^n$. Repeat this line of reasoning for $n=2,3,4$