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:

More examples