Agenda

<aside> 📌 Reminders

• Assignment 3 due November 10, 2024 </aside>

What is Induction?

Mathematical induction is a method of proving statements or formulas that apply to all natural numbers.

Steps of Simple Induction

1. Base Case: Show that the statement is true for the first natural number (usually $n = 1$).
2. Inductive Hypothesis: Assume the statement is true for some arbitrary natural number $k$.
3. Inductive Step: Use the assumption for $k$ to prove the statement is also true for $k + 1$.

Example

Let's prove that the sum of the first $n$ natural numbers is given by:

$$ 1 + 2 + \dots + n = \frac{n(n + 1)}{2}  $$

1. Base Case: For $n = 1$,

The base case holds.

$$
1 = \frac{1 \cdot (1 + 1)}{2} = 1 
$$

2. Inductive Hypothesis: Assume the formula is true for $n = k$, so

   $$ 1 + 2 + \dots + k = \frac{k(k + 1)}{2}  $$

3. Inductive Step: Prove the formula for $n = k + 1$:

   $$ 1 + 2 + \dots + k + (k + 1) = \frac{k(k + 1)}{2} + (k + 1)  $$

Simplifying, we get:

$$ = \frac{k(k + 1) + 2(k + 1)}{2} = \frac{(k + 1)(k + 2)}{2}  $$

Thus, the formula holds for $n = k + 1$.

Since both the base case and inductive step hold, the formula is proven by induction.

Practice