Step By Step Calculus » 8.3 - Induction and Summation Formulae

Synopsis
Mathematical induction is a powerful tool for proving an infinite set of assertions. An example is the claim that \displaystyle \sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}\displaystyle \sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}. This formula is really a countably infinite set of assertions:
\displaystyle n=1: \; \sum_{k=1}^{1} k = \frac{1(1+1)}{2} = 1, \quad n = 2: \; \sum_{k=1}^{2} k = \frac{2(2+1)}{2} = 3,
\displaystyle n=1: \; \sum_{k=1}^{1} k = \frac{1(1+1)}{2} = 1, \quad n = 2: \; \sum_{k=1}^{2} k = \frac{2(2+1)}{2} = 3,
and so on, for nn running through all of the natural numbers. You can think of this formula as the statement a_{n}=b_{n}a_{n}=b_{n} for all n\in {\mathbb N}n\in {\mathbb N}, where \displaystyle a_{n} = \sum_{k=1}^{n} k \displaystyle a_{n} = \sum_{k=1}^{n} k and b_{n}= \dfrac{n(n+1)}{2} b_{n}= \dfrac{n(n+1)}{2}. Note that some mathematical statements of the form a_n=b_na_n=b_n hold for n\in\mathbb{N}n\in\mathbb{N} where n\ge k_0n\ge k_0 for some k_0\in\mathbb{N}. k_0\in\mathbb{N}.
The general procedure, that we call DIRT, for doing mathematical induction are:
(Define) Identify a_{n}a_{n} and b_{n}b_{n} for all n\in {\mathbb N}n\in {\mathbb N}.
(Initial) Prove that a_{k_0}=b_{k_0}a_{k_0}=b_{k_0} for some k_0\in\mathbb{N}k_0\in\mathbb{N}.
(Reduce)Assume that a_{k}=b_{k}a_{k}=b_{k} for some arbitrary (but fixed) k\geq k_0k\geq k_0 where k\in {\mathbb N}k\in {\mathbb N}. Then, use this assumption to prove that a_{k+1}=b_{k+1}a_{k+1}=b_{k+1} for k=k_0,k_0+1,k_0+2,\cdotsk=k_0,k_0+1,k_0+2,\cdots
(Track) Conclude that a_{n}=b_{n}a_{n}=b_{n} for all n\ge k_0n\ge k_0 where n\in {\mathbb N}n\in {\mathbb N} by induction.
The same steps may be applied to prove inequalities of any form:  a_n< b_n, \; a_n\leq b_n, \; a_n>b_na_n< b_n, \; a_n\leq b_n, \; a_n>b_n or a_n\geq b_na_n\geq b_n for all n \in \mathbb{N}n \in \mathbb{N}.
Induction is used to establish the validity of summation formulas, for example if n \in \mathbb{N}n \in \mathbb{N},
• \displaystyle \sum\limits_{i=1}^{n}i=\dfrac{n(n+1)}{2}\displaystyle \sum\limits_{i=1}^{n}i=\dfrac{n(n+1)}{2}.
• \displaystyle \sum\limits_{i=1}^{n}i^2=\dfrac{n(n+1)(2n+1)}{6}\displaystyle \sum\limits_{i=1}^{n}i^2=\dfrac{n(n+1)(2n+1)}{6}.
• \displaystyle \sum\limits_{i=1}^{n}i^3=\left[\dfrac{n(n+1)}{2}\right]^2\displaystyle \sum\limits_{i=1}^{n}i^3=\left[\dfrac{n(n+1)}{2}\right]^2.
• \displaystyle \sum\limits_{i=1}^{n}r^i=\dfrac{r-r^{n+1}}{1-r}\displaystyle \sum\limits_{i=1}^{n}r^i=\dfrac{r-r^{n+1}}{1-r}, for r\neq 1r\neq 1 any fixed real number.