# how do you prove induction theory

*print*Print*list*Cite

### 1 Answer

You should know that mathematical induction is a two steps method that proves that a mathematical statement `P(n)` is valid for all natural values of n.

Considering as example that you need to check if the statement `P(n): 1^3 + 2^3 + ... + n^3 = (n(n+1)/2)^2` holds for all `n>=1` , you need to perform mathematical induction.

You need to start with the first step, called basis, and you need to prove that the statement holds for n=1 such that:

`P(1): 1^3 = (1(1+1)/2)^2 => 1 = 1` valid

Since `P(1)` holds, then you need to move to the second step called inductive step.

You need to prove that if `P(k)` holds, then `P(k+1)` also holds such that:

`P(k): 1^3 + ... + k^3 = (k(k+1)/2)^2` valid

`P(k+1):1^3 + ... + k^3 + (k+1)^3 = ((k+1)(k+2)/2)^2`

Notice that you may substitute `(k(k+1)/2)^2` for `1^3 + ... + k^3` since P(k) is valid, such that:

`P(k+1): (k(k+1)/2)^2 + (k+1)^3 = ((k+1)(k+2)/2)^2`

You need to factor out `(k+1)^2` to the left side such that:

`P(k+1): (k+1)^2(k^2/4 + k+1) =((k+1)(k+2)/2)^2`

`P(k+1): (k+1)^2(k^2 + 4k + 4)/4 = ((k+1)(k+2)/2)^2`

Notice that `k^2 + 4k + 4` is expansion of binomial `(k+2)^2` such that:

`P(k+1): (k+1)^2*(k+2)^2/4 = ((k+1)(k+2)/2)^2`

Notice that the last line proves that `P(k+1)` holds.

Since both steps hold, then, by mathematical induction, `P(n)` holds for all `n>=1` .

**Hence, all statements that involve n may be demonstrated by the two steps method called mathematical induction.**