Direct Proofs: Proofs by Contradiction and by Mathematical Induction
Direct Proofs: Proofs by Contradiction and by Mathematical Induction
Direct Proofs: Proofs by Contradiction and by Mathematical Induction
At this point, we have seen a few examples of mathematical proofs. These have the following structure: Start with the given fact(s). Use logical reasoning to deduce other facts. Keep going until we reach our goal.
Indirect Proofs
Instead of starting with the given/known facts, we start by assuming the opposite of what we seek to prove. Use logical reasoning to deduce a sequence of facts. Eventually arrive at some logical absurdity, e.g. two facts that contradict each other.
a.k.a. proof by contradiction or reductio ad absurdum Acknowledgment: The following slides are adapted from Anupam Guptas CMU course Great Ideas in Theoretical Computer Science
Mathematical Induction
n dominoes numbered 1 to n Domino Principle: Line up any number of dominos in a row; knock the first one over and they will all fall.
Fk = the kth domino falls If we set them all up in a row then we know that each one is set up to knock over the next one: For all 1 ! k < n: Fk " Fk+1
n dominoes numbered 1 to n
Fk = the kth domino falls For all 1 ! k < n: Fk " Fk+1
F1 " F2 " F3 " F1 " All Dominoes Fall
0 1 2 3 4 5 .
Plato: The Domino Principle works for an infinite row of dominoes Aristotle: Never seen an infinite number of anything, much less dominoes.
Sn & The sum of the first n odd numbers is n2. 1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2
Sn & The sum of the first n odd numbers is n2. Equivalently, Sn is the statement that:
1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2
Sn & The sum of the first n odd numbers is n2. 1 + 3 + 5 + (2k-1) + . . +(2n-1) = n2
Theorem? The sum of the first n numbers is n(n+1)/2. Try it out on small numbers! 1 1+2 1+2+3 = 1 = 1(1+1)/2. = 3 = 2(2+1)/2. = 6 = 3(3+1)/2.
1+2+3+4 = 10 = 4(4+1)/2.
Theorem? The sum of the first n numbers is n(n+1)/2. = 0 = 0(0+1)/2. 1 1+2 1+2+3 = 1 = 1(1+1)/2. = 3 = 2(2+1)/2. = 6 = 3(3+1)/2.
Notation:
(0 = 0 (n= 1 + 2 + 3 + . . . + n-1 + n
Let Sn be the statement (n =n(n+1)/2
1+2+3+4 = 10 = 4(4+1)/2.
Theorem?
Not just for proving the validity of algebraic equations. Induction is a powerful tool that can be used to prove many other sorts of statements.
Sn & {1,2,3,,n} has exactly 2n subsets. Trying to establish that: $n " 1 (Sn) Establish base case: S1 The set {1} has exactly 2 subsets: { } and {1}. 2= 21. So, S1 is true.
Sn & {1,2,3,,n} has exactly 2n subsets. Trying to establish that: $n " 1 (Sn) Assume Inductive Hypothesis: Sk {1,2,3,,k} has exactly 2k subsets. The subsets of {1,2,3,,k+1} are either subsets of {1,2,3,,k}
and there are 2k of these [by I.H.]
Sn & {1,2,3,,n} has exactly 2n subsets. Trying to establish that: $n " 1 (Sn) Assume Inductive Hypothesis: Sk {1,2,3,,k} has exactly 2k subsets. The subsets of {1,2,3,,k+1} are either subsets of {1,2,3,,k}
and there are and there are 2k 2k of these [by I.H.] of these. [by I.H.]
Sn & {1,2,3,,n} has exactly 2n subsets. Trying to establish that: $n " 1 (Sn) Assume Inductive Hypothesis: Sk {1,2,3,,k} has exactly 2k subsets. The subsets of {1,2,3,,k+1} are either subsets of {1,2,3,,k}
and there are 2k of these [by I.H.]
or A ) {k+1}, where A * {1,2,3,,k} Together, there are 2k + 2k = 2k+1 subsets. CONCLUDE: Sk+1
In Summary
We have learnt two very important proof techniques today. Proof by contradiction Proof by mathematical induction. We shall soon be seeing these on a daily basis. Learn them well!