Question

Use mathematical induction to prove that
1 + 2 + 3 + ... + n = n (n + 1) / 2
for all positive integers n.

Answer 1

Solution to Problem 1:  

Let the statement P (n) be  

1 + 2 + 3 + ... + n = n (n + 1) / 2  

STEP 1: We first show that p (1) is true.  

Left Side = 1  

Right Side = 1 (1 + 1) / 2 = 1  

Both sides of the statement are equal hence p (1) is true.  

STEP 2: We now assume that p (k) is true  

1 + 2 + 3 + ... + k = k (k + 1) / 2  

and show that p (k + 1) is true by adding k + 1 to both sides of the above statement  

1 + 2 + 3 + ... + k + (k + 1) = k (k + 1) / 2 + (k + 1)  

= (k + 1)(k / 2 + 1)  

= (k + 1)(k + 2) / 2  

The last statement may be written as  

1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2) / 2  

Which is the statement p(k + 1).