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

- The first step is 6 inches high and 6 inches deep.
- Assume steps are the same height and depth as the first step.
- 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}\)

- Verify first case: \(n=\)
- Assume induction hypothesis:
- 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\)

- Verify first case: \(n=\)
- Assume induction hypothesis:
- 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} \)

- Verify first case: \(n=\)
- Assume induction hypothesis:
- 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\)

- Verify first case: \(n=\)
- Assume induction hypothesis:
- Verify
*next*case \((n=k+1)\) by showing: