# 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. Verify that the next step is 6 inches high and 6 inches deep.

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

Staircase metaphor Math interpretation
What is first step? Verify first case $$(n=1)$$
What can we assume from first step? Assume induction hypothesis ($$n=k)$$
Does next step exist? Verify next case $$(n=k+1)$$

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

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

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

Goal for last step: $$\sum\limits_{i=1}^{k+1}{i} = \dfrac{(k+1)(k+2)}{2}$$

Finish last step starting with lefthand side:

 $$\sum\limits_{i=1}^{k+1}{i}$$ $$= \sum\limits_{i=1}^{k}{i} + \sum\limits_{i=k+1}^{k+1}{i}$$ (properties of sigma notation) $$= \sum\limits_{i=1}^{k}{i} + (k+1)$$ (computed sigma notation) $$= \dfrac{k (k+1)}{2} + (k+1)$$ (by induction hypothesis) $$= \dfrac{k (k+1)}{2} + \dfrac{2 (k+1)}{2}$$ (common denominator) $$= \dfrac{k (k+1) + 2(k+1)}{2}$$ (write as single fraction) $$= \dfrac{(k+1)(k+2)}{2}$$ (factor out k+1)

Use proof by induction to verify: $$1 + 4 + 9 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$$, i.e.,

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

1. Verify first case: $$n=$$
2. Assume induction hypothesis:
3. Verify next case $$(n=k+1)$$ by showing:

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

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

1. Verify first case: $$n=$$
2. Assume induction hypothesis:
3. Verify next case $$(n=k+1)$$ by showing:

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

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

1. Verify first case: $$n=$$
2. Assume induction hypothesis:
3. Verify next case $$(n=k+1)$$ by showing:

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

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

1. Verify first case: $$n=$$
2. Assume induction hypothesis:
3. Verify next case $$(n=k+1)$$ by showing: