Introducing Induction

Videos (~30 minutes)

Introducing Induction (8:39)
Constructing Inductive Proofs (17:03)

Optional Videos (~20 minutes)

These videos for you if you haven’t seen summation or product notation before. If you see an expression like \(\sum_{i = 0}^n i^3\) and know what that means, then you can skip these videos.

Sequences (10:23)
Sums and Products of Sequences (8:15)

Reading (~30 minutes)

DMOI Chapter 2.5, up until (and not including) “Strong Induction.”

Warmup (~50 minutes)

Problem 1

Note: you are likely to see problems very similar to this one on the quiz for Learning Target PF3.

Write the scaffolding only for a proof by induction of the following theorem:

For all \(n \geq 1\), \[ \begin{aligned} \sum_{i = 0}^n i^2 = \frac{n(n+1)(2n+1)}{6}\;. \end{aligned} \]

Please include:

A careful statement of what must be proven in the base case, in terms of the specific mathematical statement to be proven (i.e. saying “We need to show \(P(1)\)” is not enough).
A careful statement of what must be proven in the inductive step. Within the inductive step, please include:
- A statement of the inductive hypothesis, in terms of the specific mathematical statement to be proven.
- A statement of the conclusion of the inductive step, in terms of the specific mathematical statement to be proven.
You are not required to actually prove either the base case or the inductive step.

Problem 2

Note: you are likely to see problems very similar to this one on the quiz for Learning Target PF4.

Fill in the missing details for the base case and inductive step in a proof of the following theorem:

For all \(n \geq 1\), \[ \begin{aligned} \sum_{i = 0}^n 2^i = 2^{n+1} - 1\;. \end{aligned} \]

Part A

Base case: \(n = 1\). We need to prove that \(\sum_{i = 0}^1 2^i = 2^{1+1} - 1\).

Part B

Inductive step: Let \(n = k\). For the inductive hypothesis, assume that \(\sum_{i = 0}^k 2^i = 2^{k+1} - 1\). We need to prove that \(\sum_{i = 0}^{k+1} 2^i = 2^{(k+1)+1} - 1\).

Problem 3

Note: you are likely to see problems very similar to this one on the quiz for Learning Target PF5.

Write a complete proof by induction of the following theorem:

For all \(n \geq 0\), \(24|(5^{2n} - 1)\).