« previous | Monday, March 21, 2011 | next »
Review for Exam 2
- Relations (Chapter 8)
- Proofs (Lecture Notes, Chapter 4, Chapter 1.6)
- Counting (Chapter 5)
- Sequences and Summation (Chapter 2.4)
- Particularly Geometric and Harmonic sums
- Asymptotic Notation (Chapter 3)
Mathematical Induction
Goal: Prove that
is true, where
is just some predicate.
If the domain of
is the all positive integers or natural numbers, we show that
is true for the smallest in the set (1).
Basis Step: Show that
is true.
Inductive Step: Show that
is true for all
in the domain.
Conclusion: Therefore, the claim is true by induction on
.
Example
Prove that the geometric sum
when
for all
.
Proof. Let
be the statement that the sum above is correct.
Basis Step.
is true, since
Inductive Step. Suppose that
is true for some
. Our goal is to show that this implies that
is true as well.
Thus
implies
is true, so the claim follows by induction on
.
Q.E.D.
Strong Induction
Similar to regular #Mathematical Induction, only we assume a whole lot more in the inductive step:
Inductive Step. Show that
.
Examples
- Example 3 on page 286
- Example 4 on page 287
- (Ignore computational geometry examples.)
Relations
Study sections 8.1, 8.4 (skim), 8.5, and 8.6
Know the properties of a relation
on a set
:
- Reflexive

- Symmetric

- Transitive

- Antisymmetric

Counting
Chapters 5.1–5.3 (excluding combinations)
Pigeonhole Example:
Theorem: If
objects are placed into
boxes, then at least one box contains at least
objects.
Proof. Seeking a contradiction, suppose that none of the boxes contain more than
objects. Then the total number of objects is at most
Q.E.D.