PROOF BY INDUCTION · HL
Sequence and Series
Prove a sum formula by adding the next term onto the assumption.
Section 1 of 5
The method
Every proof by induction follows the same four lines.
Prove for $n = 1$
Assume for $n = k$
Prove for $n = k+1$
Conclusion: Since true for $n = 1$ and $n = k+1$ then true for all $n$.
For series: LHS = Series, RHS = Algebra. The key move at $n = k+1$ is to put in the term before — the $T_{k+1}$ term — onto the assumption.
Section 2 of 5
$1 + 2 + 3 + \dots + n = \dfrac{n}{2}(n+1)$
Prove $1 + 2 + 3 + \dots + n = \dfrac{n}{2}(n+1)$. Here $T_n = n$.
LHS = Series. RHS = Algebra.
Prove for $n = 1$:
LHS $\Rightarrow$ $n = 1$ into $T_n$ $\Rightarrow$ 1 or 2 terms.
RHS $\Rightarrow$ sub in $n = 1$:
$1 = \dfrac{1}{2}(1+1)$
$1 = 1$ True.
Assume for $n = k$:
$1 + 2 + 3 + \dots + k = \dfrac{k}{2}(k+1)$ (assumption)
Prove for $n = k+1$ — put in the term before, $T_{k+1} = (k+1)$:
$1 + 2 + 3 + \dots + k + (k+1) = \dfrac{k+1}{2}(k+1+1)$
$\dfrac{k}{2}(k+1) + \dfrac{k+1}{1} = \dfrac{k+1}{2}(k+2)$
$\dfrac{k(k+1) + 2(k+1)}{2} = \dfrac{(k+1)(k+2)}{2}$
$\dfrac{(k+1)(k+2)}{2} = \dfrac{(k+1)(k+2)}{2}$ ✓
Section 3 of 5
$1 + 3 + 5 + \dots + (2n-1) = n^{2}$
Prove $1 + 3 + 5 + \dots + (2n-1) = n^{2}$. Here $T_n = 2n-1$.
$n = 1$:
$1 = 1^{2}$ $\Rightarrow$ $1 = 1$
$n = k$:
$1 + 3 + 5 + \dots + (2k-1) = k^{2}$ (assumption, $T_k = 2k-1$)
$n = k+1$:
$1 + 3 + 5 + \dots + (2k-1) + \big(2(k+1)-1\big) = (k+1)^{2}$
$k^{2} + 2k + 1 = k^{2} + 2k + 1$
Section 4 of 5
$\displaystyle\sum_{r=1}^{n}(3r-2) = \dfrac{n}{2}(3n-1)$
Prove $\displaystyle\sum_{r=1}^{n}(3r-2) = \dfrac{n}{2}(3n-1)$, i.e. $1 + 4 + 7 + \dots + (3n-2) = \dfrac{n}{2}(3n-1)$.
$n = 1$:
$1 = \dfrac{1}{2}(2)$
$n = k$:
$1 + 4 + 7 + \dots + (3k-2) = \dfrac{k}{2}(3k-1)$ (assumption)
$n = k+1$:
$1 + 4 + 7 + \dots + (3k-2) + \big(3(k+1)-2\big) = \dfrac{k+1}{2}\big(3(k+1)-1\big)$
$\dfrac{k}{2}(3k-1) + (3k+1) = \dfrac{k+1}{2}(3k+2)$
$\dfrac{3k^{2} - k + 6k + 2}{2} = \dfrac{3k^{2} + 2k + 3k + 2}{2}$
$\dfrac{3k^{2} + 5k + 2}{2} = \dfrac{3k^{2} + 5k + 2}{2}$ ✓
Section 5 of 5
$\displaystyle\sum_{r=1}^{n} r^{2} = \dfrac{n}{6}(n+1)(2n+1)$
Prove $\displaystyle\sum_{r=1}^{n} r^{2} = \dfrac{n}{6}(n+1)(2n+1)$, $n \in \mathbb{N}$.
i.e. $1^{2} + 2^{2} + \dots + n^{2} = \dfrac{n}{6}(n+1)(2n+1)$.
$n = 1$:
$n = k$:
$1^{2} + 2^{2} + \dots + k^{2} = \dfrac{k}{6}(k+1)(2k+1)$ (assumption)
$n = k+1$:
$1^{2} + 2^{2} + \dots + k^{2} + (k+1)^{2} = \dfrac{k+1}{6}(k+2)(2k+3)$
$\dfrac{k}{6}(k+1)(2k+1) + (k+1)^{2}$
$\dfrac{k(k+1)(2k+1) + 6(k+1)^{2}}{6}$
$\dfrac{k+1}{6}\big(2k^{2} + k + 6k + 6\big)$
$\dfrac{k+1}{6}\big(2k^{2} + 7k + 6\big)$
$\dfrac{k+1}{6}(k+2)(2k+3)$ ✓
SUM
The lot in one box
The four steps
1.Prove for $n = 1$.
2.Assume for $n = k$.
3.Prove for $n = k+1$ — put in the term before ($T_{k+1}$) onto the assumption.
4.Conclusion: Since true for $n = 1$ and $n = k+1$ then true for all $n$.
5.LHS = Series, RHS = Algebra. Show the two sides meet.
End of lesson
Induction — Sequence & Series · HL · Mathslive.ie