# 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$ .