A complete proof: the sum of the first n integers

The statement to prove

We want to prove that, for every natural number n >= 1, the following property P(n) is true:

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

Step 1 - Base case (rank n = 1)

We check P(1): the sum on the left reduces to 1 (a single term). On the right, we compute 1x(1+1)/2 = 1x2/2 = 1. Both sides equal 1, so P(1) is true.

Step 2 - Inductive step

We assume that P(k) is true for some fixed integer k >= 1, that is we assume:

1 + 2 + ... + k = k(k+1)/2 (induction hypothesis)

We want to prove that P(k+1) is true, that is 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.

Inductive step calculation, term by term:

1 + 2 + ... + k + (k+1)

  = [1 + 2 + ... + k] + (k+1)
  = k(k+1)/2 + (k+1)             (we use the induction hypothesis here)
  = (k+1) x [ k/2 + 1 ]
  = (k+1) x [ (k+2)/2 ]
  = (k+1)(k+2)/2                 (this is exactly what we wanted to show)

We have therefore shown that P(k) true entails P(k+1) true.

Conclusion

By the principle of induction, since P(1) is true (base case) and P(k) true entails P(k+1) true for all k >= 1 (inductive step), we conclude that P(n) is true for every integer n >= 1.

Numerical check

For n = 4: the sum 1+2+3+4 = 10, and the formula gives 4x5/2 = 20/2 = 10. For n = 7: the sum 1+2+3+4+5+6+7 = 28, and the formula gives 7x8/2 = 56/2 = 28. Both methods agree.

Common pitfall

In the inductive step, you must actually USE the induction hypothesis at a precise moment of the calculation (here, by replacing "1 + 2 + ... + k" with "k(k+1)/2"): an inductive step that never relies on the hypothesis P(k) generally has no chance of succeeding, and often signals a writing mistake.