More Induction

Videos (~40 minutes)

Inductive Proofs of Inequalities (10:28)
Inductive Proofs of Algorithmic Correctness (11:52)
Inductive Proofs of Solutions to Recurrence Relations (6:52)
The Inductive Step Never goes Backwards (7:01)

Reading (~30 minutes)

Chapter 5 of Connecting Discrete Mathematics and Computer Science by David Liben-Nowell, up to page 23.
- This reading primarily adds more examples to our discussion of induction, with no major new concepts. It’s ok to skim it and get comfortable with the examples.

Warmup (~50 minutes)

Problem 1

Use induction to prove the following theorem:

Theorem 1 Let \(r \in \mathbb{R}\). Then,

\[ \begin{aligned} \sum_{i=0}^{n} r^i = \begin{cases} \frac{1 - r^{n+1}}{1 - r} & \text{if } r \neq 1, \\ n + 1 & \text{if } r = 1. \end{cases} \end{aligned} \]

Problem 2

Consider the following theorem:

Theorem 2 For all \(n \geq h\), \(n! \geq n^2\).

Please (a) determine the smallest value of \(h \in \mathbb{Z}\) that makes this theorem true. Then (b) prove the theorem using mathematical induction.