Proofs
Table of Contents
A proof is a sequence of propositions, each of which follows from the preceding ones by a valid law of reasoning. A proof may use basic facts that we assume without proof (these are called axioms), as well as other facts that we have previously proved (lemmas).
1. Direct Proof
A direct proof proves \(P \implies Q\) by first assuming \(P\) to be true, then following a sequence of logical steps to get to \(Q\).
Example: Divisibility of two integers
Theorem: For any integers \(a, b, c\) with \(a \neq 0\), if \(a \mid b\) and \(a \mid c\) then \(a \mid (b + c)\).
Proof: Let \(a, b, c\) be arbitrary integers with \(a \neq 0\). Assume that \(a \mid b\) and \(a \mid c\). Then we can say that \(b=aq_1\) and \(c = aq_2\) for integers \(q_1, q_2\). Hence, we have:
\begin{align} b + c &= aq_1 + aq_2 \notag \\ &= a(q_1 + q_2) \notag \end{align}Since \(q_1 + q_2\) is an integer, this implies \(a \mid (b+c)\). \(\square\)
Example: Divisibility rule for 11
Theorem: Given a number, delete the last digit and subtract it from the remaining number. Denote by \(\text{reduce}(n)\) the number obtained from \(n\) with this rule. Then, \(n\) is divisible by \(11\) if and only if \(\text{reduce}(n)\) is also divisible by \(11\).
Proof: To prove this, we need to prove both that:
- (i) \(\forall n \geq 10, \: 11 \mid n \implies 11 \mid \text{reduce}(n)\)
- (ii) \(\forall n \geq 10, \: 11 \mid \text{reduce}({n}) \implies 11 \mid n\)
First, we prove (i). Assume that \(11 \mid n\). Write \(n\) as \([n']d\), where \(d\) is the last digit of \(n\) and \(n'\) are the other digits. Then, the following is true:
\begin{align} \text{reduce}(n) &= n'-d \notag \\ n &= 10n' + d \notag \end{align}Adding these two equations, we get that:
\begin{align} \text{reduce}(n) + n = 11n' \notag \end{align}Thus, \(11 \mid (\text{reduce}(n) + n)\). Since \(11 \mid n\), we know that \(11 \mid \text{reduce}(n)\) (by lemma from previous example).
For (ii), we assume that \(11 \mid \text{reduce}(n)\). Using the fact that \(11 \mid (\text{reduce}(n) + n)\) exactly as before, we find that \(11 \mid n\). \(\square\)
2. Proof by Contraposition
Since we know that the contrapositive of an implication is logically equivalent to itself, we can prove \(\lnot Q \implies \lnot P\) instead of proving \(P \implies Q\).
Example: Even and odd
Theorem: Let \(n\) be an integer. If \(n^2-4n+7\) is even, then \(n\) is odd.
Proof: We will proceed by contraposition. We assume that \(n\) is even, and we want to prove that \(n^2 - 4n + 7\) is odd.
Then, \(n^2-4n+7\) becomes the sum of two evens and one odd number, which is clearly odd. \(\square\)
Example: Inequalities
Theorem: For a real number \(x\), if \(x^3-x > 0\) then \(x > -1\).
Proof: By contraposition, we assume that \(x \leq -1\) and prove that \(x^3-x \leq 0\). Then:
\begin{align} x^3 - x = x(x^2- 1) \notag \end{align}If \(x \leq -1\), then \(x\) is negative and \(x^2 - 1\) is nonnegative, and thus \(x(x^2-1) \leq 0\). \(\square\)
3. Proof by Contradiction
Also called reductio ad absurdum, the goal is to prove \(P\) by instead finding a contradiction with \(\lnot P\). The process is to first assume \(\lnot P\) is true. Then, we get two results, \(R\) and \(\lnot R\), to be true at the same time; but since \(\lnot P \implies (R \land \lnot R)\) is false, then by the law of the excluded middle \(P\) must be true.
Example: Infinitely many primes
Theorem [Euclid]: There are infinitely many primes.
Proof: We will proceed by contradiction. We assume that there are only finitely many primes. Call these primes \(p_1, p_2, \dots , p_k\).
Define \(q = p_1p_2 \cdots p_k + 1\). Since all our primes are included in \(p_1, p_2, \dots , p_k\), \(q\) cannot be prime.
Therefore, \(q\) must have a prime divisor \(d > 1\). By our assumption, then, \(d = p_i\) for some \(1 \leq i \leq k\). Hence, \(d \mid (q - 1)\) and \(d \mid q\). Therefore, \(d \mid 1\) so \(d = 1\). But, since \(d\) has to be a prime divisor \(d > 1\), we have a contradiction, as desired. Hence, our initial assumption was false, i.e. there exists infinitely many primes. \(\square\)
Example: Irrational number
Theorem: \(\sqrt{2}\) is irrational.
Proof: We will proceed by contradiction. Assume that \(\sqrt{2}\) is rational. Then, we can write \(\sqrt{2} = \frac{a}{b}\) for integers \(a, b\) that have no common factors.
Squaring this, we get \(2 = \frac{a^2}{b^2} \Rightarrow 2b^2 = a^2\). Hence, \(a^2\) is even. It is clear that if \(a^2\) is even, then \(a\) is even (the proof of this fact shall be left as an exercise). So, we can write \(a = 2c\) for some integer \(c\). Thus,
\begin{align} a^2 &= 2b^2 \notag \\ 4c^2 &= 2b^2 \notag \\ 2c^2 &= b^2 \notag \end{align}Then, \(b^2\) is even, which means \(b\) is also even. However, since \(a\) and \(b\) share no common factors, \(a\) and \(b\) cannot both be even, and thus we have a contradiction. \(\square\)
4. Proof by Cases
Here the goal is to prove \(P\) by dividing the situation into multiple cases. If we can prove that the theorem works for all the cases, then we have proved the theorem works for the entire situation. Note that this only works if the cases cover the entire situation.
Example: Absolute value
Theorem: For all real \(x\), \(|x+3| - x \geq 3\).
Proof: We shall proceed by cases.
Case (i): \(x \geq -3\)
Then, \(|x + 3| - x = x + 3 - x = 3 \geq 3\).
Case (ii): \(x < -3\)
Then, \(|x+3| - x = -2x - 3 > -3 + 6 = 3\). \(\square\)
Example: Exponentiating irrational numbers
Theorem: There exists irrational numbers \(x, y\) such that \(x^y\) is rational.
Proof: Take the value \(\sqrt{2}^{\sqrt{2}}\). We shall proceed by cases:
Case (i): \(\sqrt{2}^{\sqrt{2}}\) is rational
Here, we are immediately done, because the theorem works for \(x=y=\sqrt{2}\).
Case (ii): \(\sqrt{2}^{\sqrt{2}}\) is irrational
Here, we take \(x = \sqrt{2}^{\sqrt{2}}\) which is irrational, and \(y = \sqrt{2}\). Then, \(x^y = \left ( \sqrt{2}^{\sqrt{2}}\right ) ^{\sqrt{2}} = \sqrt{2}^2 = 2\), which is rational. \(\square\)
This is an example of a non-constructive proof, as it doesn't tell you what \(x\) and \(y\) will be, it just tells you that they exist.
5. Proof by Induction
Oftentimes when we want to prove that a statement is true over a set, we can use proof by induction. This involves proving some base case, such as when \(n = 0\). Then, we perform what is known as the inductive step, where we assume the inductive hypothesis that the theorem is true for \(n = k\), where \(k\) is some arbitrary number. Then, using this assumption, we prove that the theorem must be true for \(n = k+1\). If this can be done, the knowing \(n=0\) is true along with knowing that if \(n=k\) is true, then \(n=k+1\) is true means that \(n=1, 2, 3, \dots\) are all true, which proves the theorem.
Example: Sum of squares
Theorem: \(\forall n \in \mathbb{N}, \: \sum_{i=0}^{n} u^2 = \frac{1}{6}n(n+1)(2n+1)\)
Proof: We shall proceed by induction. The base case \(n=0\) is true since:
\begin{align} \sum_{i=0}^{0}i^2 = \frac{1}{6}(0)(1)(1) = 0 \notag \end{align}Next, we assume that \(n=k\) is true, and we want to prove that \(n=k+1\) is true. Then:
\begin{align} \sum_{i=0}^{k+1}i^2 = \sum_{i=0}^ki^2+(k+1)^2 &= \frac{1}{6}k(k+1)(2k+1) + (k+1)^2 \notag \\ &= \frac{1}{6}(k+1)\left[k(2k+1)+6(k+1)\right] \notag \\ &= \frac{1}{6}(k+1)\left[2k^2 + 7k + 6\right] \notag \\ &= \frac{1}{6}(k+1)(k+2)(2k+3) \notag \end{align}This completes the inductive step, and we are done. \(\square\)
Example: Sum of interior angles
Theorem: For all \(n \geq 3\), the sum of the interior angles of a convex polygon with \(n\) sides is \((n-2)\pi\).
Proof: We shall proceed by induction. For our base case \(n=3\), we know that the angle sum of a triangle is \(\pi\), which is consistent with the theorem.
Next, assuming that the theorem is true for \(n=k\), we want to show that it is also true for \(n=k+1\). Consider the following \((k+1)\text{-gon}\):
If we "chop off"° a triangle as shown, we have a \(k\text{-gon}\) and a triangle. So, the interior angle sum of a \((k+1)\text{-gon}\) is just:
\begin{align} \pi + (k-2)\pi &= (k-1)\pi \notag \\ &= (k+1-2)\pi \notag \end{align}This completes the inductive step, and we are done. \(\square\)
5.1. Strengthening the Induction Hypothesis
Sometimes, it is hard to prove the given theorem's inductive hypothesis. In these cases, we can try to prove a stronger version of it, such that if we prove that version, the original theorem must also be true.
Example: Sum of reciprocal squares
Theorem: \(\forall n \geq 1, \: \sum_{i=1}^{n} \frac{1}{i^2} \leq 2\)
Proof: We modify the theorem to show that \(\forall n \geq 1, \: \sum_{i=1}^n \frac{1}{i^2} \leq 2 - \frac{1}{n}\). If we prove this stronger condition, then we have also proven the original theorem.
We proceed by induction. The base case \(n=1\) holds as \(\sum_{i=1}^{1}\frac{1}{i^2} = 1 \leq 2 -1 = 1\).
Then, assuming that \(n=k\) is true, we want to prove that \(n=k+1\) is true:
\begin{align} \sum_{i=1}^{k+1}\frac{1}{i^2} = \sum_{i=1}^k\frac{1}{i^2} + \frac{1}{(k+1)^2} &\leq 2 - \frac{1}{k} + \frac{1}{(k+1)^2} \notag \\ &\leq 2 - \frac{1}{k+1} \notag \end{align}This completes the inductive step, and we are done. \(\square\)
5.2. Strong Induction
Sometimes, it is insufficient to just assume that the theorem works for \(n=k\). Strong induction modifies the inductive hypothesis such that for arbitrary \(k\), we assume that \(\land_{i=0}^k P(i)\) is true.
Example: Quicksort
Theorem: \(\text{Quicksort}(A)\) correct sorts an array \(A\) of length \(n\).
Proof: We proceed by strong induction. The base case of \(0\) and \(1\) both hold since you just do nothing.
Then we want to prove \(n=k+1\) for \(k \geq 1\), assuming that \(n \leq k\) are all true. Then, each subarray to quicksort has length in \({0, 1, \dots, k}\). Then, these subarrays return correctly sorted arrays (by the inductive hypothesis), thus the final array is correctly sorted. \(\square\)
Example: Fibonacci numbers
Theorem: For all \(n \geq 0\), the n-th Fibonacci number \(F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}\), where \(\phi, \psi\) are the roots of \(x^2-x-1\), i.e. \(\phi = \frac{1+\sqrt{5}}{2}\) and \(\psi = \frac{1-\sqrt{5}}{2}\).
Proof: We proceed via strong induction. The base cases of \(n=0\) and \(n=1\) work:
\begin{align} F(0) &= \frac{\phi^0-\psi^0}{\sqrt{5}} = \frac{1-1}{\sqrt{5}} = 0 \notag \\ F(1) &= \frac{\phi^1-\psi^1}{\sqrt{5}} = \frac{\sqrt{5}}{\sqrt{5}} = 1 \notag \end{align}Now, assuming that \(F(n) = \frac{\phi^n-\psi^n}{\sqrt{5}}\) and \(F(n-1) = \frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}\), we want to prove that \(F(n+1) = \frac{\phi^{n+1}-\psi^{n+1}}{\sqrt{5}}\). Then:
\begin{align} F(n+1) &= F(n) + F(n-1) \notag \\ &= \frac{\phi^n - \psi^n}{\sqrt{5}} + \frac{\phi^{n-1}-\psi^{n+1}}{\sqrt{5}} \notag \\ &= \frac{1}{\sqrt{5}}\left( \phi^n - \psi^n + \phi^{n-1} - \psi^{n-1}\right) \notag \end{align}Without loss of generality, if \(\phi^2 = \phi + 1\), then \(\phi^{n+1} = \phi^n + \phi^{n-1}\). Therefore, we have
\begin{align} = \frac{1}{\sqrt{5}}\left(\phi^{n+1}-\psi^{n+1}\right) \: \square \notag \end{align}