Mathematical Induction

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

Explanation

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

Examples

Proving the formula for the sum of a series

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

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

A:

1. When $n=1$, $1^{3}=1={\tfrac {1}{4}}(1)^{2}((1)+1)^{2}={\tfrac {1}{4}}(4)=1$, so it is true for $n=1$
2. Suppose that the statement is true for $k,k\in \mathbb {N}$. That is, suppose that $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 $n=k+1$ (that is, prove that $1^{3}+2^{3}+3^{3}+\cdots +(k+1)^{3}={\tfrac {1}{4}}(k+1)^{2}(k+2)^{2}$:

   ${\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 $n$.