# Proof by Induction & the Infinite Staircase

How does one construct an infinite staircase? (answer: one step at a time)

1. The first step is 6 inches high and 6 inches deep.
2. Assume steps are the same height and depth as the first step.
3. Check that the next step is 6 inches high and 6 inches deep.

Staircase metaphor Math interpretation
What is first step? Check the first case, $$n=1$$
What can we assume from first step? Assume induction hypothesis works for $$n=k$$
Does next step exist? Check next case, i.e., check $$n=k+1$$ still works

Use proof by induction to verify: $$\sum\limits\limits_{i=1}^{n}{1} = n$$

1. Check first: $$\sum\limits_{i=1}^{1}{1} \stackrel{?}{=} 1$$

$$\sum\limits_{i=1}^{1}{1} = 1$$ and $$n = 1$$. Verified!

2. Assume: $$\sum\limits_{i=1}^{k}{1} = k$$

3. Check next: $$\sum\limits_{i=1}^{k+1}{1} \stackrel{?}{=} k+1$$

\begin{aligned} \sum\limits_{i=1}^{k+1}{1} &= \sum\limits_{i=1}^{k}{1} + \sum\limits_{i=k+1}^{k+1}{1} &\text{(properties of sigma notation)} \\ &= \sum\limits_{i=1}^{k}{1} + 1 &\text{(computed last sigma)} \\ &= k + 1 &\text{(substituted induction hypothesis)} \end{aligned}
Verified!

Use proof by induction to verify: $$\sum\limits_{i=1}^{n}{c} = c \cdot n$$ where $$c$$ is a constant.

1. Check first: $$\sum\limits_{i=1}^{1}{c} \stackrel{?}{=} c \cdot 1$$

$$\sum\limits_{i=1}^{1}{c} = c$$ and $$c \cdot n = c \cdot 1$$. Verified!

2. Assume: $$\sum\limits_{i=1}^{k}{c} = c \cdot k$$

3. Check next: $$\sum\limits_{i=1}^{k+1}{c} \stackrel{?}{=} c(k+1)$$

\begin{aligned} \sum\limits_{i=1}^{k+1}{c} &= \sum\limits_{i=1}^{k}{c} + \sum\limits_{i=k+1}^{k+1}{c} &\text{(properties of sigma notation)} \\ &= \sum\limits_{i=1}^{k}{1} + \color{blue}{\text{ ______}} & \text{(computed last sigma)} \\ &= \color{blue}{\text{ ______}} + c &\text{(substituted induction hypothesis)} \\ &= c(k + 1) &\text{(used distributive property of mult. & add)} \end{aligned}
Verified!

Use proof by induction to verify: $$\sum\limits\limits_{i=1}^{n}{i} = \dfrac{n (n+1)}{2}$$.

1. Check first: $$\sum\limits_{i=1}^{1}{i} \stackrel{?}{=} \dfrac{1 (1+1)}{2}$$

$$\sum\limits_{i=1}^{1}{i} = 1$$ and $$\frac{1 (1+1)}{2} = \frac{2}{2} = 1$$. Verified!

2. Assume: $$\sum\limits_{i=1}^{k}{i} = \dfrac{k (k+1)}{2}$$

3. Check next: $$\sum\limits_{i=1}^{k+1}{i} \stackrel{?}{=} \dfrac{(k+1) (k+2)}{2}$$

\begin{aligned} \sum\limits_{i=1}^{k+1}{i} &= \sum\limits_{i=1}^{k}{i} + \sum\limits_{i=k+1}^{k+1}{i} &\text{(properties of sigma notation)} \\ &= \sum\limits_{i=1}^{k}{i} + \color{blue}{\text{ ______}} &\text{(computed sigma notation)} \\ &= \color{blue}{\text{ ______}} + (k+1) &\text{(substituted induction hypothesis)} \\ &= \dfrac{k (k+1)}{2} + \dfrac{2 (k+1)}{2} &\text{(common denominator)} \\ &= \dfrac{k (k+1) + 2(k+1)}{2} &\text{(written as single fraction)} \\ &= \dfrac{(k+1)(k+2)}{2} &\text{(factor out k+1)} \end{aligned}
Verified!

Use proof by induction to verify sum of squares: $$1 + 4 + 9 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$$, that is,

$$\sum\limits_{i=1}^{n}{i^2} = \dfrac{n(n+1)(2n+1)}{6}$$

1. Check first:
2. Assume:
3. Check next:

Use proof by induction to verify: $$1 + 3 + 5 + ... + (2n-1) = n^2$$, that is,

$$\sum\limits_{i=1}^{n}{(2i-1)} = n^2$$

1. Check first:
2. Assume:
3. Check next:

Use proof by induction to verify: $$2 + 4 + 6 + ... + (2n) = n^2+n$$, that is,

$$\sum\limits_{i=1}^{n}{2i} = n^2+n$$

1. Check first:
2. Assume:
3. Check next:

Use proof by induction to verify: $$1 + 8 + 27 + ... + n^3 = \frac{n^2(n+1)^2}{4}$$, that is,

$$\sum\limits_{i=1}^{n}{i^3} = \dfrac{n^2(n+1)^2}{4}$$

1. Check first:
2. Assume:
3. Check next: