Skip to main content

Section 6.2 Induction Examples

Subsection 6.2.1 Summations

Induction can be used to prove various summation formulas.

By induction, for \(n = 1\text{,}\) we have,

\begin{equation*} \sum_{i=1}^1 i = 1 = \frac{1(1 + 1)}{2} \end{equation*}

Then, assume the result is true for some \(n = k \in \mathbb{N}\text{,}\) and we want to show that,

\begin{align*} \sum_{i=1}^{k+1} \amp = \frac{(k + 1)((k + 1) + 1)}{2}\\ \amp = \frac{(k + 1)(k + 2)}{2} \end{align*}

Then,

\begin{align*} 1 + 2 + \dots + (k - 1) + k + (k + 1) \amp = \frac{k(k + 1)}{2} + (k + 1) \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{k(k + 1)}{2} + \frac{2(k + 1)}{2} \amp\amp \text{writing over a common denominator}\\ \amp = \frac{k^2 + 3k + 2}{2} \amp\amp \text{combining fractions and simplifying}\\ \amp = \frac{(k + 1)(k + 2)}{2} \amp\amp \text{factoring the quadratic expression} \end{align*}

By induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

By induction, for \(n = 1\text{,}\) we have,

\begin{equation*} \sum_{i=1}^1 i^2 = 1 = \frac{1(1 + 1)(2 + 1)}{6} \end{equation*}

Then, assume the result is true for some \(n = k \in \mathbb{N}\text{.}\) We want to show that,

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 = \sum_{i=1}^{k+1} i^2 \amp = \frac{(k + 1)(k + 2)(2(k + 1) + 1)}{6}\\ \amp = \frac{(k + 1)(k + 2)(2k + 3)}{6} \end{align*}

Then,

\begin{align*} 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2 \amp = \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{k(k + 1)(2k + 1)}{6} + \frac{6(k + 1)^2}{6} \amp\amp \text{writing over a common denominator}\\ \amp = \frac{k(k+1)(2k + 1) + 6(k+1)^2}{6} \amp\amp \text{combining fractions}\\ \amp = \frac{(k + 1) \brac{k(2k + 1) + 6(k + 1)}}{6} \amp\amp \text{factoring out $(k + 1)$}\\ \amp = \frac{(k + 1)(2k^2 + 7k + 6)}{6} \amp\amp \text{expanding and simplifying}\\ \amp = \frac{(k + 1)(k + 2)(2k + 3)}{6} \amp\amp \text{factoring the quadratic expression} \end{align*}
Thus, by induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

By induction, for \(n = 1\) (and \(r \neq 1\)) we have,

\begin{equation*} \sum_{i=1}^1 r^{i-1} = r^0 = 1 = \frac{r - 1}{r - 1} \end{equation*}

Then, assume the result is true for some \(n = k \in \mathbb{N}\text{.}\) Then, we want to show that,

\begin{equation*} 1 + r + r^2 + \dots + r^{k-1} + r^k = \frac{r^{k+1} - 1}{r - 1} \end{equation*}

Then,

\begin{align*} 1 + r + r^2 + \dots + r^{k-1} + r^k \amp = \sum_{i=1}^{k+1} r^{i-1}\\ \amp = \sum_{i=1}^k r^{i-1} + r^k \amp\amp \text{separating off the final term}\\ \amp = \frac{r^k - 1}{r - 1} + r^k \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{r^k - 1}{r - 1} + \frac{r^k(r - 1)}{r - 1} \amp\amp \text{combining the fractions over a common denominator}\\ \amp = \frac{r^{k+1} - 1}{r - 1} \amp\amp \text{simplifying} \end{align*}

Thus, by induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

By induction, for \(n = 1\text{,}\) we have,

\begin{equation*} \sum_{i=1}^1 i^3 = 1^3 = 1 = \brac{\frac{1(1 + 1)}{2}}^2 \end{equation*}

Then, assume that the result is true for some \(n = k \in \mathbb{N}\text{.}\) Then, we want to show that,

\begin{align*} 1^3 + 2^3 + \dots + (k - 1)^3 + k^3 + (k + 1)^3 = \sum_{i=1}^{k+1} i^3 \amp = \brac{\frac{(k + 1)(k + 2)}{2}}^2\\ \amp = \frac{(k + 1)^2(k + 2)^2}{4} \end{align*}

Then,

\begin{align*} 1^3 + 2^3 + \dots + (k - 1)^3 + k^3 + (k + 1)^3 \amp = \frac{k^2(k + 1)^2}{4} + (k + 1)^3 \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{k^2(k + 1)^2}{4} + \frac{4(k + 1)^3}{4} \amp\amp \text{writing over a common denominator}\\ \amp = \frac{k^2(k + 1)^2 + 4(k + 1)^3}{4} \text{combining fractions}\\ \amp = \frac{(k + 1)^2 (k^2 + 4k + 4)}{4} \amp\amp \text{factoring $(k + 1)^2$ from both terms}\\ \amp = \frac{(k + 1)^2(k + 2)^2}{4} \amp\amp \text{factoring the quadratic expression} \end{align*}

Thus, the result is true for all \(n \in \mathbb{N}\text{.}\)

Subsection 6.2.2 Other Examples

By induction, for \(n = 1\text{,}\) we have,

\begin{equation*} (1 + x)^1 = 1 + x \geq 1 + 1 \cdot x \end{equation*}

Then, assume that our result is true for \(n = k \in \mathbb{N}\text{,}\) and we want to show that,

\begin{equation*} (1 + x)^{k+1} \geq 1 + (k + 1)x \end{equation*}

Then,

\begin{align*} (1 + x)^{k+1} \amp = (1 + x)^k(1 + x)\\ \amp \geq (1 + kx)(1 + x) \amp\amp \text{as $(1 + x)^k \geq 1 + kx$ and $1 + x > 0$}\\ \amp = 1 + x + kx + x^2\\ \amp = 1 + (k + 1)x + kx^2\\ \amp \geq 1 + (k + 1)x \amp\amp \text{as $kx^2 \geq 0$} \end{align*}

By induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

By induction, for \(n = 5\text{,}\) we have \(2^5 = 32 \geq 25 = 5^2\text{.}\)

Then, assume the result is true for some \(n = k \in \mathbb{N}, k \geq 5\text{.}\) Then, we want to show that,

\begin{equation*} 2^{k+1} \geq (k+1)^2 \end{equation*}

Then,

\begin{align*} 2^{k+1} \amp = 2 \cdot 2^k\\ \amp \geq 2 \cdot k^2 \amp\amp \text{by the induction hypothesis} \end{align*}

Then, we want to show that this quantity \(2k^2\) is greater than or equal to the desired result \((k + 1)^2\text{.}\) In other words,

\begin{gather*} 2k^2 \geq (k + 1)^2\\ 2k^2 \geq k^2 + 2k + 1\\ k^2 \geq 2k + 1 \end{gather*}

To prove this, we can show that \((k - 1)^2 \geq 2\text{.}\) Since \(k \geq 5\text{,}\) we have \((k - 1)^2 \geq (5 - 1)^2 = 4^2 \geq 2\text{.}\) Then,

\begin{align*} 2^{k+1} \amp \geq 2k^2\\ \amp = k^2 + k^2\\ \amp \geq k^2 + 2k + 1 \amp\amp \text{as $k^2 \geq 2k + 1$}\\ \amp = (k + 1)^2 \end{align*}

Thus, by induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

By induction, for \(n = 4\text{,}\)

\begin{equation*} 4! = 24 > 16 = 2^4 \end{equation*}

Then, assume that the result is true for some \(n = k \in \mathbb{N}, k \geq 4\text{.}\) Then, we want to show that,

\begin{equation*} (k + 1)! > 2^{k+1} \end{equation*}

Then,

\begin{align*} (n + 1)! \amp = (n + 1)n!\\ \amp > (n + 1) \cdot 2^n \amp\amp \text{by the induction hypothesis}\\ \amp > 2 \cdot 2^n \amp\amp \text{since $n \geq 4$, $n + 1 \geq 5 > 2$}\\ \amp = 2^{n + 1} \end{align*}

Thus, by induction, the result is true for all \(n \in \mathbb{N}, n \geq 4\text{.}\)

By induction, for \(n = 1\text{,}\) we have,

\begin{equation*} \sum_{i=1}^1 \frac{1}{i(i + 1)} = \frac{1}{1(1 + 1)} = \frac{1}{2} = \frac{1}{1 + 1} \end{equation*}

Then, assume the result is true for some \(n = k \in \mathbb{N}\text{.}\) Then, we want to show that,

\begin{equation*} \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{k(k + 1)} + \frac{1}{(k + 1)(k + 2)} = \sum_{i=1}^{n+1} \frac{1}{i(i + 1)} = \frac{k + 1}{k + 2} \end{equation*}

Then,

\begin{align*} \amp \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{k(k + 1)} + \frac{1}{(k + 1)(k + 2)}\\ \amp = \sum_{i=1}^{k+1} \frac{1}{i(i+1)}\\ \amp = \sum_{i=1}^k \frac{1}{i(i+1)} + \frac{1}{(k+1)(k+2)}\\ \amp = \frac{k}{k + 1} + \frac{1}{(k + 1)(k + 2)} \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{k(k + 2)}{(k + 1)(k + 2)} + \frac{1}{(k + 1)(k + 2)}\\ \amp = \frac{k^2 + 2k + 1}{(k + 1)(k + 2)}\\ \amp = \frac{(k + 1)^2}{(k + 1)(k + 2)}\\ \amp = \frac{k + 1}{k + 2} \end{align*}

By induction, for \(n = 1\text{,}\) we have,

\begin{equation*} \frac{1}{\sqrt{1}} = 1 \geq \sqrt{1} \end{equation*}

Then, assume the result is true for some \(n \in \mathbb{N}\text{.}\) Then, we want to show that,

\begin{equation*} \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \dots + \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{n + 1}} \geq \sqrt{n + 1} \end{equation*}

Then,

\begin{align*} \amp \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \dots + \frac{1}{\sqrt{n}} + \frac{1}{\sqrt{n + 1}}\\ \amp \geq \sqrt{n} + \frac{1}{\sqrt{n + 1}} \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{\sqrt{n} \cdot \sqrt{n + 1} + 1}{\sqrt{n + 1}}\\ \amp \geq \frac{\sqrt{n} \sqrt{n} + 1}{\sqrt{n + 1}} \amp\amp \text{as $\sqrt{n + 1} \geq \sqrt{n}$}\\ \amp = \frac{n + 1}{\sqrt{n + 1}}\\ \amp = \sqrt{n + 1} \end{align*}

Thus, by induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

By induction, for \(n = 0\text{,}\) \(\sum_{i=0}^0 i \cdot 3^i = 0 = \frac{3^1(2 \cdot 0 - 1) + 3}{4}\text{.}\)

Then, assume the result is true for some \(n = k \in \mathbb{N}\text{.}\) We want to show that,

\begin{equation*} \sum_{i=0}^{k+1} i \cdot 3^i = \frac{3^{k+2}(2(k+1) - 1) + 3}{4} = \frac{3^{k+2}(2k + 1) + 3}{4} \end{equation*}

Then,

\begin{align*} \sum_{i=0}^{k+1} i \cdot 3^i \amp = \sum_{i=0}^k i \cdot 3^i + \sum_{i=k+1}^{k+1} i \cdot 3^i\\ \amp = \frac{3^{k+1}(2k - 1) + 3}{4} + (k+1) 3^{k+1} \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{3^{k+1}(2k - 1) + 3 + 4(k+1) 3^{k+1}}{4}\\ \amp = \frac{(6k + 3)3^{k+1} + 3}{4}\\ \amp = \frac{3^{k+1}(2k + 1) + 3}{4} \end{align*}

Thus, by induction, the result is true for all \(n \in \mathbb{Z}, n \geq 0\text{.}\)

Subsection 6.2.3 Divisibility Examples

We will prove the result for odd positive integers (for odd $n \in \mathbb{N}$). Then, the result for odd negative integers follows directly, because \((-n)^2 - 1 = n^2 - 1\text{.}\)

By induction, for \(n = 1\text{,}\) we have \(n^2 - 1 = 1^2 - 1 = 0\text{,}\) which is a multiple of 8.

Then, assume the result is true for some odd \(n = k \in \mathbb{N}\text{,}\) that \(k^2 - 1\) is a multiple of 8. Then, we want to show that for the next odd integer, which is \(k + 2\text{,}\) that \((k + 2)^2 - 2\) is divisible by 8. Then,

\begin{align*} (k + 2)^2 - 1 \amp = k^2 + 4k + 3 \amp\amp \text{expanding and simplifying} \end{align*}

To use the induction hypothesis, split up the terms into \(k^2 - 1\text{,}\) and the leftover terms,

\begin{align*} \amp = (k^2 - 1) + 4k + 4\\ \amp = (k^2 - 1) + 4(k + 1) \end{align*}

By the induction hypothesis, \(k^2 - 1\) is divisible by 8. Also, \(k\) is odd, so \(k + 1\) is even, and so \(4(k + 1) = 4(2l) = 8l\) for some \(l \in \mathbb{Z}\text{,}\) which is divisible by 8. Then, their sum \((k^2 - 1) + 4(k + 1)\) is divisible by 8.

Thus, by induction, the result is true for all odd integers \(n\text{.}\)

By induction, for \(n = 2\text{,}\) we have \(3 \mid (2^3 - 2)\text{,}\) or \(3 \mid 6\text{,}\) which is true.

Then, assume the result is true for some \(n = k \in \mathbb{N}\text{,}\) that is, \(3 \mid (k^3 - k)\text{.}\) We want to show that,

\begin{equation*} 3 \mid ((k + 1)^3 - (k + 1)) \end{equation*}

Then,

\begin{align*} (k + 1)^3 - (k + 1) \amp = (k^3 + 3k^2 + 3k + 1) - k - 1\\ \amp = k^3 + 3k^2 + 2k\\ \amp = k(k^2 + 3k + 2)\\ \amp = k(k + 1)(k + 2) \end{align*}

Then, \(k(k+1)(k+2)\) is the product of 3 consecutive integers. Then, one of \(k, k+1, k+2\) must be divisible by 3, so \(k(k+1)(k+2)\) is divisible by 3, and so \(3 \mid ((k + 1)^3 - (k + 1))\text{.}\) Thus, the result is true for all \(n \in \mathbb{N}, n \geq 2\text{.}\)

Notice that we didn't explicitly use the induction hypothesis here. However, the proof that the product of 3 consecutive integers is divisible by 3 can be shown using math induction.

By induction, for \(n = 1\text{,}\) \(n^3 - n = 1^3 - 1 = 0\text{,}\) which is divisible by 6.

Then, assume that the result is true for some \(n = k \in \mathbb{N}\text{,}\) that is, \(k^3 - k\) is divisible by 6. Then,

\begin{align*} (k + 1)^3 - (k + 1) \amp = (k^3 + 3k^2 + 3k + 1) - k - 1 \amp\amp \text{expanding}\\ \amp = k^3 + 3k^2 + 2k \amp\amp \text{simplifying} \end{align*}

To use the induction hypothesis, split up the terms into \(k^3 - k\text{,}\) and the leftover terms,

\begin{align*} \amp = (k^3 - k) + (3k^2 + 3k)\\ \amp = (k^3 - k) + 3k(k + 1) \end{align*}

By the induction hypothesis, \(k^3 - k\) is divisible by 6. Also, one of \(k\) and \(k + 1\) is even, and so \(k(k + 1)\) is even, so \(k(k + 1) = 2m\) for some \(m \in \mathbb{Z}\text{.}\) Then, \(3k(k + 1) = 3(2m) = 6m\) is divisible by 6. Then, the sum \((k^3 - k) + 3k(k+1)\) is divisible by 6.

Thus, by induction, the result is true for all \(n \in \mathbb{N}\text{.}\)

Subsection 6.2.4 Geometric Examples

By induction, for \(n = 1\text{,}\) 1 line subdivides the plane into 2 regions, and,

\begin{equation*} 2 = \frac{1(1 + 1)}{2} + 1 \end{equation*}

Then, assume the result is true for \(n = k \in \mathbb{N}\text{.}\) We want to show that \(k+1\) lines in general position subdivide the plane into the \(\frac{(k + 1)(k + 2)}{2} + 1\) regions. The \((k+1)\)st line intersects the other \(k\) lines each at 1 point, for \(k\) total intersections, and that form \((k+1)\) boundary lines, that each divide a subdivision into 2 segments each, i.e. create \((k+1)\) new regions. Then,

\begin{align*} S_{k+1} \amp = S_k + (k + 1)\\ \amp = \frac{k(k + 1)}{2} + 1 + (k + 1) \amp\amp \text{by the induction hypothesis}\\ \amp = \frac{k(k + 1)}{2} + \frac{2(k + 2)}{2}\\ \amp = \frac{(k + 1)(k + 2)}{2} \end{align*}

For \(n = 3\text{,}\) the sum of the angles in a triangle is \(180 = 180(3 - 2)\) Then, assume the result is true for some \(n\text{,}\) and consider an \((n + 1)\)-sided polygon. Let \(S_n\) be the sum of the interior angles of an \(n\)-gon. Then, we want to show that,

\begin{equation*} S_{n+1} = 180((n + 1) - 2) = 180(n - 1) \end{equation*}

Then, “collapse” two sides into one, to split the \((n+1)\)-gon into an \(n\)-gon, and a triangle. Then,

\begin{align*} S_{n+1} \amp = S_n + S_3 \end{align*}

By the induction hypothesis, \(S_n = 180(n-2)\text{,}\) and by the base case, \(S_3 = 180\text{,}\)

\begin{align*} S_{n+1} \amp = 180(n - 2) + 180 \amp\amp \text{by the induction hypothesis, and the base case}\\ \amp = 180(n - 1) \end{align*}

Thus, by induction, the result is true for all \(n \in \mathbb{N}, n \geq 3\text{.}\)

By induction, for \(n = 1\text{,}\) a length \(\sqrt{1} = 1\) is the unit length, which is given. Then, assume that we can construct a length \(\sqrt{n}\) using straightedge and compass. Then, construct a right angle, using the compass. Extend the two sides of the right angle to be a unit length and length \(\sqrt{n}\text{.}\) Then, connect the ends to form a right triangle, with legs of length 1 and \(\sqrt{n}\text{.}\) By the Pythagorean theorem, the hypotenuse has length \(\sqrt{n+1}\text{.}\)

This is related to the Spiral of Theodorus