Using the principle of mathematical induction, prove each of the following for all n ϵ N:
1 + 2 + 3 + 4 + … + n = 1/2 n(n + 1)
To Prove:
1 + 2 + 3 + 4 + … + n = 1/2 n(n + 1)
Steps to prove by mathematical induction:
Let P(n) be a statement involving the natural number n such that
(i) P(1) is true
(ii) P(k + 1) is true, whenever P(k) is true
Then P(n) is true for all n ϵ N
Therefore,
Let P(n): 1 + 2 + 3 + 4 + … + n = 1/2 n(n + 1)
Step 1:
P(1) = 1/2 1(1 + 1) = 1/2 × 2 = 1
Therefore, P(1) is true
Step 2:
Let P(k) is true Then,
P(k): 1 + 2 + 3 + 4 + … + k = 1/2 k(k + 1)
Now,
1 + 2 + 3 + 4 + … + k + (k + 1) = 1/2 k(k + 1) + (k + 1)
= (k + 1){ 1/2 k + 1}
= 1/2 (k + 1) (k + 2)
= P(k + 1)
Hence, P(k + 1) is true whenever P(k) is true
Hence, by the principle of mathematical induction, we have
1 + 2 + 3 + 4 + … + n = 1/2 n(n + 1) for all n ϵ N
Hence proved.