# Mathematical Induction

Induction is a form of proof useful for proving equations involving non-closed expressions (i.e., expressions with ${\displaystyle n}$ terms; sequences).

## Explanation

Induction involves first proving that the equation is true for ${\displaystyle n=1}$, then proving true for ${\displaystyle n=k+1}$ (assuming for the purpose of the proof that the equation holds true for ${\displaystyle n=k}$). Since it is true for ${\displaystyle n=k}$ and true for ${\displaystyle n=k+1}$, and also true for ${\displaystyle n=1}$, it is true for ${\displaystyle n=2}$. It follows that it is true for all positive integers ${\displaystyle n}$.

### Examples

#### Proving the formula for the sum of a series

Q: Prove by mathematical induction that for all integers ${\displaystyle n\geq 1}$,

${\displaystyle 1^{3}+2^{3}+3^{3}+4^{3}+\cdots +n^{3}=(1+2+3+....n)^{2}}$

A:

1. When ${\displaystyle n=1}$, ${\displaystyle 1^{3}=1={\tfrac {1}{4}}(1)^{2}((1)+1)^{2}={\tfrac {1}{4}}(4)=1}$, so it is true for ${\displaystyle n=1}$
2. Suppose that the statement is true for ${\displaystyle k,k\in \mathbb {N} }$. That is, suppose that ${\displaystyle 1^{3}+2^{3}+3^{3}+4^{3}+\cdots +k^{3}={\tfrac {1}{4}}k^{2}(k+1)^{2}}$. This is sometimes called the induction hypothesis.
3. Then prove the statement for ${\displaystyle n=k+1}$ (that is, prove that ${\displaystyle 1^{3}+2^{3}+3^{3}+\cdots +(k+1)^{3}={\tfrac {1}{4}}(k+1)^{2}(k+2)^{2}}$:
{\displaystyle {\begin{aligned}{\mbox{LHS}}&=1^{3}+2^{3}+3^{3}+4+3+\cdots +k^{3}+(k+1)^{3}\\&={\tfrac {1}{4}}k^{2}(k+1)^{2}+(k+1)^{3}&{\mbox{ (by the induction hypothesis)}}\\&={\tfrac {1}{4}}(k+1)^{2}(k^{2}+4(k+1))\\&={\tfrac {1}{4}}(k+1)^{2}(k^{2}+4k+4)\\&={\tfrac {1}{4}}(k+1)^{2}(k+2)^{2}\\&={\mbox{RHS}}\end{aligned}}}
4. It follows from parts 1 and 2 by mathematical induction that the statement is true for all positive integers ${\displaystyle n}$.