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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall n P(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.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Thus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(k)} implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(k+1)} is true, so the claim follows by induction on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} on a set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} :

• Reflexive Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,x)\in R \ \forall x \in A}
• Symmetric Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y)\in R \rightarrow (y,x) \in R}
• Transitive Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y),(y,z) \in R \rightarrow (x,z) \in R}
• Antisymmetric Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x,y)\in R \wedge (y,z)\in R \rightarrow x=z}

Counting

Chapters 5.1–5.3 (excluding combinations)

Pigeonhole Example:

Theorem: If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} objects are placed into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} boxes, then at least one box contains at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lceil N/k \rceil} objects.

Proof. Seeking a contradiction, suppose that none of the boxes contain more than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lceil N/k \rceil -1} objects. Then the total number of objects is at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k(\lceil N/k \rceil - 1) < k((N/k+1)-1) = N}

Q.E.D.