Proofs¶
10/12/2020 -
Definitions:
- Statements to be proved or already proved:
- Theorem
- Proposition
- Lemma
- Corollary (immediately follows from proof of theorem)
- Statements assumed to be true:
- Axiom
- Postulate
Induction¶
Weak Induction: Prove base cases, then prove inductive steps.
Ex. Prove that the sum of the first m odd numbers \(S(m)\) is equal to \(m^2\).
- B.S. m = 1, \(1 = 1^2\).
- I.S. Assume \(S(m) = m^2\) for some \(m \geq 1\).
- \(S(m + 1) = S(m) + 2(m+1)-1\)
- \(=m^2+2m+2-1\)
- \(=m^2+2m+1\)
- \(=(m+1)^2\).
Strong Induction: Prove all cases less than current case implies current case.
Ex. Prove \(\forall m > 1, m\) is divisible by a prime.
Consider any \(m > 1\):
- m is a prime. QED.
- m is not a prime: \(m = a * b\), where \(a,b < m\) and \(a, b > 1\)
- By IH, \(a\) is divsible by a prime \(P\)
- \(P | a\) and \(a | m\), so \(P | m\). QED.
Contrapositive¶
Rather than proving \(p \implies q\), prove \(\lnot q \implies \lnot p\).
Ex. \(p^2 \text{ is even} \implies p \text{ is even}\)
Contradiction¶
Prove that the opposite statement causes a contradiction.
Ex. Prove that \(\sqrt{2}\) is irrational.
- Assume that \(\sqrt{2} = \frac{p}{q}, p, q \in N\) with no common factor
- \(p^2 = 2q^2\)
- \(p^2\) is even
- \(p\) is even
- \(p = 2k\)
- \(\sqrt{2} = \frac{2k}{q}\)
- \(q^2 = \frac{(2k)^2}{2} = 2k^2\)
- \(q^2\) is even
- \(q\) is even
- \(2 | p\) and \(2 | q\), so by contradiction \(\sqrt{2}\) is not rational.
Pidgeonhole Principle¶
Given n containers and m items, if m > n, at least one container must have more than one item in it.
Ex. For any m, there exists a multiple of m that is a sequence of 1s followed by a sequence of 0s in binary.
- For some m, consider the sequence
1 11 111 ... 111...11
where the last item is of length m+1 - if you divide by m, there are only m remainders possible: [0..m-1]
- There are m+1 items in the sequence but only m possible remainders, so two items in the sequence will have the same remainder
- Let \(a = k_1m + r, b=k_2m+r, a > b\)
- \(\therefore a-b = (k_1-k_2)m\)
- \(a-b\) is a multiple of m and of form
111...00