CSCE 222 Lecture 20

From Notes
Jump to navigation Jump to search

« 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 ∀nP(n) is true, where P(n) is just some predicate.

If the domain of P is the all positive integers or natural numbers, we show that P is true for the smallest in the set (1).

Basis Step: Show that P(1) is true.

Inductive Step: Show that P(k)→P(k+1) is true for all k in the domain.

Conclusion: Therefore, the claim is true by induction on k.

Example

Prove that the geometric sum

∑j=0nrj=rn+1−1r−1

when r≠1 for all n≥0.

Proof. Let P(n) be the statement that the sum above is correct.

Basis Step. P(0) is true, since

∑j=00rj=r1−1r−1=1

Inductive Step. Suppose that P(k) is true for some k≥0. Our goal is to show that this implies that P(k+1) is true as well.

∑j=0k+1rj=1+r+r2+…+rk⏟+rk+1=rk+1−1r−1+rk+1by inductive hypothesis=rk+1−1+rk+2−rk+1r−1=rk+2−1r−1

Thus

P(k)

implies

P(k+1)

is true, so the claim follows by induction on

k

.

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 P(0)∧P(1)∧…∧P(k)→P(k+1).

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 R on a set A:

  • Reflexive (x,x)∈R ∀x∈A
  • Symmetric (x,y)∈R→(y,x)∈R
  • Transitive (x,y),(y,z)∈R→(x,z)∈R
  • Antisymmetric (x,y)∈R∧(y,z)∈R→x=z


Counting

Chapters 5.1–5.3 (excluding combinations)

Pigeonhole Example:

Theorem: If N objects are placed into k boxes, then at least one box contains at least ⌈N/k⌉ objects.

Proof. Seeking a contradiction, suppose that none of the boxes contain more than

⌈N/k⌉−1

objects. Then the total number of objects is at most

k(⌈N/k⌉−1)<k((N/k+1)−1)=N
Q.E.D.