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 $\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)\rightarrow 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\neq 1$ for all $n\geq 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\geq 0$. Our goal is to show that this implies that $P(k+1)$ is true as well.

${\begin{aligned}\sum _{j=0}^{k+1}r^{j}&=\underbrace {1+r+r^{2}+\ldots +r^{k}} +r^{k+1}\\&={\frac {r^{k+1}-1}{r-1}}+r^{k+1}&{\mbox{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{aligned}}$

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 \ldots \wedge P(k)\rightarrow 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\ \forall x\in A$
• Symmetric $(x,y)\in R\rightarrow (y,x)\in R$
• Transitive $(x,y),(y,z)\in R\rightarrow (x,z)\in R$
• Antisymmetric $(x,y)\in R\wedge (y,z)\in R\rightarrow 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.