Introduction to Induction

Videos (~40 mins)

Introduction to sequences (6:13)
The sum and product of finite sequences (9:20)
Intro to Mathematical Induction (12:15)

Readings (~30 mins)

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

Warmup (~40 mins)

Problem 1

Part A

Here are three attempted statements of a theorem which was provided in the video (it is also Example 2.5.1 in DMOI). None of these statements are correct. For each one, explain which piece is incorrect, why it matters, and how to fix it.

“Theorem 1”: For all integers \(n \in \mathbb{Z}\),

\[ \sum_{i = 0}^n i = \frac{n(n+1)}{2}\;. \]

“Theorem 2”: For all natural numbers \(n \geq 1\),

\[ \sum_{i = 0}^n i = \frac{i(i+1)}{2}\;. \]

“Theorem 3”: For all natural numbers \(n \geq 1\),

\[ \sum_{i = 0}^n i = \frac{n(n-1)}{2}\;. \]

Part B

Here are three attempted inductive proofs of the correct theorem. None of them are correct. For each one, explain what’s wrong.

“Proof 1:” Suppose that \(n = 1\). Then,

\[ \begin{aligned} \sum_{i = 0}^n i &= \sum_{i = 1}^n i \\ &= 1 \\ &= \frac{1(1+1)}{2}\;, \end{aligned} \]

as was to be shown. This completes the proof.

“Proof 2:” Suppose that the theorem holds for some \(n = k\). We’ll show that this implies that it also holds for \(n = k+1\). We can calculate

\[ \begin{aligned} \sum_{i = 0}^{k+1} i &= \sum_{i = 0}^k i + (k+1) &\text{(manipulating sum)} \\ &= \frac{k(k+1)}{2} + (k+1) &\text{(inductive hypothesis)} \\ &= \frac{(k+1)(k+2)}{2} &\text{(algebra)} \\ &= \frac{(k+1)((k+1) + 1)}{2} &\text{(algebra)}\;. \end{aligned} \]

This shows that the statement is true for \(n = k+1\), which completes the proof.

“Proof 3:” First, we’ll do the base case. Suppose that \(n = 1\). Then,

\[ \begin{aligned} \sum_{i = 0}^n i &= \sum_{i = 1}^n i \\ &= 1 \\ &= \frac{1(1+1)}{2}\;. \end{aligned} \]

So, the statement is true for \(n = 1\), completing the base case. Now we’ll do the inductive step. Suppose that the statement is true for \(n = k+1\). We’ll show that it’s also true for \(n = k\). We can calculate

\[ \begin{aligned} \sum_{i = 0}^{k+1} i &= \frac{(k+1)(k+2)}{2} &\text{(inductive hypothesis)} \\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} &\text{(algebra)}\;. \end{aligned} \]

Since what’s left includes the formula for the case \(n = k\), this completes the inductive step.

Problem 2

Use mathematical induction to prove that, for any integer \(n >= 1\),

\[ \begin{aligned} \sum_{i = 0}^n 2^i = 2^{n+1} - 1 \end{aligned} \]