Prove 1 + 2 + 3 + ... + n = n(n+1) / 2 for all n >= 1

Background: This proof is often used for the analysis of various algorithms.

Example: 1 + 2 + ... + 100 = (100 * 101) / 2

If we wanted to write this equality as a part of a program, it could be created as either of the following snippets.

sum = 0
for i = 1 to 100:
    sum += i
print sum

which is the same as

print n * (n + 1) / 2

Both of these code snippets print the same value at the end, and it is possible to mathematically prove which is more efficient.

Now, without further adieu, here is a proof that demonstrates how we can show this.

Prove: 1 + 2 + 3 + ... + n = (n (n + 1)) / 2 for all n ≥ 1.

Base case: Observe 1 = (1 * 2) / 2.
Let k ≥ 1 be some integer.
Assume 1 + 2 + 3 + ... + k = (k (k + 1)) / 2
We want to show that 1 + 2 + 3 + ... + k + (k + 1) = ((k + 1) * (k + 2)) / 2.
Notice that 1 + 2 + ... + k + (k + 1) = (k (k + 1)) / 2 + k + 1 = ((k + 1) * (k + 2)) / 2.

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

By the proof of mathematical induction, 1 + 2 + 3 + ... + n = (n (n + 1)) / 2 for all n ≥ 1.

---

From here: Using this same proof technique, it is possible to demonstrate that this is also true for strings. For example, we can prove that (Uⁿ)^R = (U^R)ⁿ.