Induction with series

The principle of mathematical induction, the steps and setting out of an induction proof, proving formulas for series written in sigma notation, and forming a conjecture to prove.

The principle

The base case knocks over the first domino. The inductive step guarantees each domino knocks over the next. Both steps are essential.

Proving a series formula

Example 1●●

Prove by induction that for all positive integers $n$, $$1 + 3 + 5 + \cdots + (2n - 1) = n^2.$$

Step 1, $n = 1$. LHS $= 1$ and RHS $= 1^2 = 1$, so it is true for $n = 1$.

Step 2. Assume it is true for $n = k$, where $k$ is a positive integer. That is, assume $$1 + 3 + \cdots + (2k - 1) = k^2. \qquad (*)$$

Prove it for $n = k + 1$, that is, prove $1 + 3 + \cdots + (2k - 1) + (2k + 1) = (k + 1)^2$.

LHS $= k^2 + (2k + 1)$, using $(*)$. This is $(k + 1)^2$, which is the RHS.

Conclusion. By the principle of mathematical induction, the statement is true for all positive integers $n$.

Example 2: sigma notation●●●

Prove that $\displaystyle\sum_{r=1}^{n} r(r + 1) = \tfrac13 n(n + 1)(n + 2)$ for all $n \ge 1$.

$n = 1$: LHS $= 1 \times 2 = 2$ and RHS $= \tfrac13 \times 1 \times 2 \times 3 = 2$.

Assume $\displaystyle\sum_{r=1}^{k} r(r + 1) = \tfrac13 k(k + 1)(k + 2)$.

Then $\displaystyle\sum_{r=1}^{k+1} r(r + 1) = \tfrac13 k(k + 1)(k + 2) + (k + 1)(k + 2)$.

Take out the common factor: $= \tfrac13 (k + 1)(k + 2)(k + 3)$, which is the formula with $n = k + 1$.

So by induction it is true for all $n \ge 1$.

Forming a conjecture

Example 3●●

Find a formula for $S_n = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} + \cdots + \dfrac{1}{n(n + 1)}$.

$S_1 = \tfrac12$, $S_2 = \tfrac23$, $S_3 = \tfrac34$.

Conjecture: $S_n = \dfrac{n}{n + 1}$. This would then be proved by induction, using $\dfrac{k}{k + 1} + \dfrac{1}{(k + 1)(k + 2)} = \dfrac{k(k + 2) + 1}{(k + 1)(k + 2)} = \dfrac{k + 1}{k + 2}$.

Flashcards

The two steps of induction

Base case: true for $n = 1$. Inductive step: if true for $n = k$, then true for $n = k + 1$.

Inductive step for a series

$S_{k+1} = S_k + T_{k+1}$, then use the assumption for $S_k$.

$displaystylesum_{r=1}^{n} r$

$\tfrac12 n(n + 1)$

$displaystylesum_{r=1}^{n} r^2$

$\tfrac16 n(n + 1)(2n + 1)$

Practice

In Example 2, what is the LHS when $n = 1$?
Using the conjecture in Example 3, find $S_4$.
Evaluate $1 + 3 + 5 + \cdots + 39$.
Evaluate $\displaystyle\sum_{r=1}^{10} r^2$.
Evaluate $\displaystyle\sum_{r=1}^{100} r$.
In the inductive step, the assumption is that the statement is true for:
For $\displaystyle\sum_{r=1}^{n} r^3$, the $(k + 1)$th term is:
A proof shows the inductive step but skips the base case. Then:
To finish the inductive step for Example 2, the expression $\tfrac13 k(k + 1)(k + 2) + (k + 1)(k + 2)$ should be: