Proofs

Premises.

1. If it does not rain or it is not foggy, then the sailing race is held and the lifesaving demonstration goes on.
2. If the sailing race is held, then the trophy is awarded.
3. The trophy was not awarded.

Conclusion. It rained.

Variables. $R$ = "it rains," $F$ = "it is foggy," $S$ = "sailing race held," $L$ = "lifesaving demo on," $T$ = "trophy awarded."

Formalised premises.

1. $(\lnot R \lor \lnot F) \to (S \land L)$
2. $S \to T$
3. $\lnot T$

Goal. Derive $R$.

1. $\lnot T$   [Premise 3]
2. $S \to T$   [Premise 2]
3. $\lnot S$   [Modus Tollens, 1 & 2]
4. $\lnot S \lor \lnot L$   [Addition, 3]
5. $\lnot (S \land L)$   [De Morgan, 4]
6. $(\lnot R \lor \lnot F) \to (S \land L)$   [Premise 1]
7. $\lnot(\lnot R \lor \lnot F)$   [Modus Tollens, 5 & 6]
8. $R \land F$   [De Morgan + double negation, 7]
9. $R$   [Simplification, 8] ∎

Example. If $n$ is odd, then $n^2$ is odd.

Proof. Assume $n$ is odd. Then $n = 2k+1$ for some integer $k$. Then $$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$$ Since $2k^2 + 2k$ is an integer, $n^2$ has the form $2m+1$, i.e., $n^2$ is odd. ∎

Example. Show that the square of an even integer is even.

Proof. Let $n = 2k$. Then $n^2 = 4k^2 = 2(2k^2)$. Hence $n^2$ is even. ∎

Example. If $n^2$ is even, then $n$ is even. (Contrapositive of "$n$ odd ⟹ $n^2$ odd.")

Proof (contrapositive). Assume $n$ is odd. Write $n = 2k+1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1$ is odd. Hence $\lnot(n \text{ even}) \to \lnot(n^2 \text{ even})$. By contraposition, $n^2$ even ⟹ $n$ even. ∎

Example. If $3n+2$ is even, then $n$ is even.

Proof (contrapositive). Suppose $n$ is odd. Then $n = 2k+1$, so $3n+2 = 6k+3+2 = 6k+5 = 2(3k+2)+1$, which is odd. Contrapositive proven; original follows. ∎

Example. $\sqrt{2}$ is irrational.

Proof. Suppose, for contradiction, that $\sqrt{2} = a/b$ in lowest terms (so $\gcd(a,b)=1$). Squaring: $2b^2 = a^2$, so $a^2$ is even, so $a$ is even (by the previous example). Write $a = 2c$. Then $2b^2 = 4c^2$, so $b^2 = 2c^2$, so $b^2$ is even, so $b$ is even. But $a, b$ both even contradicts $\gcd(a,b)=1$. ∎

Example. $\log_2 3$ is irrational.

Proof. Suppose $\log_2 3 = p/q$ with $p,q \in \mathbb{Z}$, $q \neq 0$. Then $2^{p/q} = 3$, so $2^p = 3^q$. LHS is even (assuming $p \geq 1$), RHS is odd — contradiction. If $p = 0$, $2^0 = 1 \neq 3^q$ for any $q$. ∎

Example. If $3n+2$ is even, then $n$ is even (by contradiction).

Proof. Suppose $3n+2$ is even but $n$ is odd. Then $n = 2k+1$, so $3n+2 = 6k+5 = 2(3k+2)+1$ is odd. Contradicts "$3n+2$ even." ∎

Example. For every integer $n$, $n \leq n^2$.

Proof (by cases).

• Case 1: $n \geq 1$. Multiply $n \geq 1$ by the positive number $n$ to get $n^2 \geq n$.
• Case 2: $n = 0$. Then $0 = 0^2$ ✓.
• Case 3: $n \leq -1$. Then $n < 0$ but $n^2 \geq 1 > 0$, so $n < n^2$. ✓

All integers covered. ∎

Example. The square of any integer leaves remainder 0 or 1 modulo 4.

Proof. Every integer is $4k, 4k+1, 4k+2,$ or $4k+3$.

• $(4k)^2 = 16k^2 \equiv 0\pmod 4$.
• $(4k+1)^2 = 16k^2 + 8k + 1 \equiv 1 \pmod 4$.
• $(4k+2)^2 = 16k^2 + 16k + 4 \equiv 0 \pmod 4$.
• $(4k+3)^2 = 16k^2 + 24k + 9 \equiv 1 \pmod 4$.

Hence the only remainders are 0 and 1. ∎

Example. $1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$ for all $n \geq 1$.

Base. $n=1$: LHS $=1$, RHS $= 1 \cdot 2 / 2 = 1$ ✓.

Step. Assume $1 + \cdots + k = k(k+1)/2$. Then $$1+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}.$$ So $P(k+1)$ holds. ∎

Strong induction. Sometimes you assume $P(0), P(1), \ldots, P(k)$ to derive $P(k+1)$. Equivalent in power to ordinary induction but often easier to apply.

Example. Every integer $n \geq 2$ is a product of primes. Base: $2$ is prime. Step: assume the claim for all $2 \leq m \leq k$. If $k+1$ is prime, done. Else $k+1 = ab$ with $2\leq a, b \leq k$; by IH, $a$ and $b$ each factor into primes, so $k+1$ does too. ∎

Swap.

temp := x
x := y
y := temp

Precondition: $x = a \land y = b$ for some specific values $a, b$.
After line 1: $\text{temp} = a, x = a, y = b$.
After line 2: $\text{temp} = a, x = b, y = b$.
After line 3: $\text{temp} = a, x = b, y = a$.
Postcondition $x = b \land y = a$ achieved. ✓

Example. Prove that the following code computes $n!$:

i := 1
fact := 1
while i <= n:
    fact := fact * i
    i := i + 1
// claim: fact == n!

Invariant: $\text{fact} = (i-1)!$ and $1 \leq i \leq n+1$.

• Init. Before loop: $i=1$, $\text{fact}=1=0!=(i-1)!$. ✓
• Maintenance. Suppose $\text{fact}=(i-1)!$. Body sets $\text{fact} \gets \text{fact}\cdot i = (i-1)!\cdot i = i!$ and then $i \gets i+1$. After: $\text{fact} = (i_{\text{new}}-1)!$. ✓
• Termination. Loop exits when $i > n$, i.e., $i = n+1$. Then $\text{fact} = (i-1)! = n!$. ✓

Done. ∎

Example. Linear search returns the smallest index of $\text{target}$ in $A[1..n]$ (or $-1$).

i := 1
while i <= n:
    if A[i] == target: return i
    i := i + 1
return -1

Invariant: $\text{target} \notin A[1..i-1]$.

• Init. $i=1$, $A[1..0]$ is empty, so vacuously target not in it.
• Maintenance. Before iteration: target not in $A[1..i-1]$. If $A[i]=\text{target}$, we return correctly. Else, target not in $A[1..i]$; we increment $i$.
• Termination. If loop exits without finding, $i = n+1$, so target $\notin A[1..n]$. Return $-1$ is correct.