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: