how do you prove induction theory
1 Answer | Add Yours
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.
Join to answer this question
Join a community of thousands of dedicated teachers and students.Join eNotes