# CSCE 222 Lecture 20

« 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.**