Sum of First n Integers

The sum $1 + 2 + 3 + ... + n$ equals $\frac{n(n+1)}{2}$. This is one of the most useful formulas in competitive programming.

For example, $1 + 2 + ... + 100 = \frac{100 \times 101}{2} = 5050$. You get the answer without a loop.

Why does this work? Pair the first and last terms: $1 + 100 = 101$, $2 + 99 = 101$, and so on. You have $50$ pairs, each summing to $101$, giving $50 \times 101 = 5050$. The formula generalizes this pairing trick.