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\):

  1. m is a prime. QED.
  2. m is not a prime: \(m = a * b\), where \(a,b < m\) and \(a, b > 1\)
    1. By IH, \(a\) is divsible by a prime \(P\)
    2. \(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.

  1. Assume that \(\sqrt{2} = \frac{p}{q}, p, q \in N\) with no common factor
  2. \(p^2 = 2q^2\)
  3. \(p^2\) is even
  4. \(p\) is even
  5. \(p = 2k\)
  6. \(\sqrt{2} = \frac{2k}{q}\)
  7. \(q^2 = \frac{(2k)^2}{2} = 2k^2\)
  8. \(q^2\) is even
  9. \(q\) is even
  10. \(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