You need to use mathematical induction to prove the formula for every positive integer n, hence, you need to perform the two steps of the method, such that:
Step 1: Basis: Show that the statement P(n) hold for n = 1, such that:
`1 = 1(1+1)/2 => 1 = 1*2/2 => 1=1`
Step 2: Inductive step: Show that if P(k) holds, then also P(k + 1) holds:
`P(k): 1 + 2 + .. + k = (k(k+1))/2` holds
`P(k+1): 1 + 2 + ... + k + (k+1) = ((k+1)(k+2))/2`
You need to use induction hypothesis that P(k) holds, hence, you need to re-write the left side, such that:
`(k(k+1))/2 + k + 1 = ((k+1)(k+2))/2`
`k(k+1) + 2k + 2 = k^2 + 2k + k + 2`
`k^2 + k + 2k + 2 = k^2 + 2k + k + 2`
Notice that P(k+1) holds.
Hence, since both the basis and the inductive step have been verified, by mathematical induction, the statement `P(n): 1 + 2 + 3 + ... + n = (n(n+1))/2` holds for all positive integers n.
No comments:
Post a Comment