how do you prove induction theory   

1 Answer

sciencesolve's profile pic

sciencesolve | Teacher | (Level 3) Educator Emeritus

Posted on

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.