We teach you how to use mathematical induction to prove algebraic properties. This technique is very useful and simple to use. We offer examples and exercises to help you understand proofs by induction.
Induction reasoning is often used to prove sequence properties.
Learn about how to use mathematical induction
In many mathematical situations, we need to prove a property $P(n)$ for any natural number $n$. In most cases, a direct approach to do this is very difficult. To overcome these difficulties, we mainly use induction reasoning. In fact, we only verify that the property $ P (0),$ for $ n = 0,$ is true. Then assume that $ P (n), $ is true as well. Finally, verify that $ P (n + 1) $ is also satisfied, that’s all.! We notice that sometimes we verify $P(1)$, mainly if the property $P(n)$ is not defined at $n=0$.
Example: let us show that for any $n\in\mathbb{N},$ \begin{align*}\tag{P(n)} (n+1)!\ge \sum_{k=1}^n k!. \end{align*}
For $n=1,$ we have $(1+1)!=2!\ge 1!,$ hence the property $P(1)$ is satisfied. Assume now, by induction, that $P(n)$ holds. As $n+2>2,$ then \begin{align*}\tag{1} (n+2)!=(n+2)(n+1)!\ge 2(n+1)!.\end{align*}
On the other hand, by adding $(n+1)!$ to the both sides of the inequality $P(n),$ we obatin \begin{align*}\tag{2}2(n+1)!\ge \sum_{k=1}^nk!+(n+1)!=\sum_{k=1}^{n+1}k!\end{align*}
By combining (1) et (2), we obtain \begin{align*} (n+2)!\ge \sum_{k=1}^{n+1}k!.\end{align*}
Thus $P(n+1)$ holds.
Exercises on induction reasoning
In the following exercises, we show you how to use mathematical induction to prove some known formulas and inequalities.
Exercise: Prove by induction that \begin{align*} A_n&=1+2+\cdots+n=\frac{n(n+1)}{2}\cr & B_n=1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}.\end{align*}
Proof: We have $A_1=1=\frac{1(1+1)}{2},$ it is true. Assume, by induction, that the expression of $A_n$ as above, and determine that of $A_{n+1}$. We have \begin{align*}A_{n+1}&=1+2+\cdots+n+(n+1)=S_n+(n+1)\cr &=\frac{n(n+1){2}}+(n+1)=\frac{n(n+1)+2(n+1)}{2}\cr &= \frac{(n+1)(n+2)}{2}=\frac{(n+1)((n+1)+1)}{2}.\end{align*} Thus the induction hypothesis is also true for $A_{n+1}$. This ends the proof.
Similarly, we have $B_1=1=\frac{1(1+1)(2\times 1+1)}{6}$. Assume, by the induction, the $B_n$ is true and prove that $B_{n+1}$ is also true. We have \begin{align*} B_{n+1}&=B_n+ (n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2\cr & =\frac{n(n+1)(2n+1)+6(n+1)^2}{6}\cr &=\frac{(n+1)(n(2n+1)+6(n+1))}{6}\cr &=\frac{(n+1)(2n^2+7n+6)}{6}.\end{align*} But $(n+2)(2n+3)=2n^2+7n+6$. Thus \begin{align*} B_{n+1}&=\frac{(n+1)(n+2)(2n+3)}{6}\cr & =\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}.\end{align*} This ends the proof.
