How does one construct an infinite staircase? (answer: one step at a time)
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}\)
Use proof by induction to verify: \(1 + 3 + 5 + ... + (2n-1) = n^2\), that is,
\(\sum\limits_{i=1}^{n}{(2i-1)} = n^2\)
Use proof by induction to verify: \(2 + 4 + 6 + ... + (2n) = n^2+n\), that is,
\(\sum\limits_{i=1}^{n}{2i} = n^2+n\)
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} \)
More examples