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 $\mathrm{\forall }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)\to 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

$\sum _{j=0}^n{r}^j=\frac{r^{n+1}-1}{r-1}$

when $r\ne 1$ for all $n\ge 0$.

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

Basis Step. $P(0)$ is true, since

$\sum _{j=0}^0{r}^j=\frac{r^1-1}{r-1}=1$

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

$\begin{array}{rl}\sum _{j=0}^{k+1}{r}^j& =\underbrace{1+r+r^2+\dots +r^k}+r^{k+1}\\ & =\frac{r^{k+1}-1}{r-1}+r^{k+1}& \text{by inductive hypothesis}\\ & =\frac{\cancel{r^{k+1}}-1+r^{k+2}\cancel{-r^{k+1}}}{r-1}\\ & =\frac{r^{k+2}-1}{r-1}\end{array}$

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)\wedge P(1)\wedge \dots \wedge P(k)\to 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)\in R\mathrm{\forall }x\in A$
• Symmetric $(x,y)\in R\to (y,x)\in R$
• Transitive $(x,y),(y,z)\in R\to (x,z)\in R$
• Antisymmetric $(x,y)\in R\wedge (y,z)\in R\to 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 $\lceil N/k\rceil$ objects.

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

$\lceil N/k\rceil -1$

objects. Then the total number of objects is at most

$k(\lceil N/k\rceil -1)<k((N/k+1)-1)=N$

Q.E.D.