The Sum of the First N Integers

Adding up 1 through N does not require a loop. Four different proofs of the closed form, from Gauss's pairing trick to a telescoping sum, plus the overflow trap that bites the naive implementation.

The first version of this function that most people write is a loop:

function sumTo(n) { let total = 0; for (let i = 1; i <= n; i++) total += i; return total; }

It is correct, and for small n nobody will ever notice the cost. But the loop is doing work that does not need doing. The answer has a closed form, and the closed form has been known for a very long time.

These values are called the triangular numbers, for a reason Proof 2 makes visible.

Checking a few values is not a proof, though. It is evidence. Below are four genuine proofs, each of which teaches something slightly different.

The story, probably apocryphal, is that a schoolteacher told a young Carl Friedrich Gauss to add the numbers from 1 to 100 to keep him busy, and he answered almost immediately. What he noticed is that the sequence pairs up neatly from the outside in:

Every pair sums to 101, and there are 50 such pairs, so the total is (50 \cdot 101 = 5050).

Stated in general: the first and last terms sum to (n + 1), the second and second-to-last sum to (n + 1), and so on. There are (n/2) pairs, giving (\frac{n}{2}(n+1)).

That argument has a hole in it. If (n) is odd there is a leftover middle term with no partner, and (n/2) is not a whole number of pairs. The usual fix is to split into cases, but there is a cleaner way to write the same idea that never mentions parity at all.

Write the sum forwards, write it again backwards underneath, and add the two lines column by column:

Every column contains a pair that sums to (n + 1), and there are exactly (n) columns:

No case split, no leftover middle term. The doubling absorbed the parity problem: (n(n+1)) is the product of two consecutive integers, so it is always even, and the division always comes out whole.

The same argument again, without algebra.

Stack the sum as a staircase of dots: one dot in the first row, two in the second, and so on down to (n) in the last row. The number of dots is (S) by construction.

Now take a second copy of the same staircase, rotate it 180 degrees, and slot it into the gap above the first one:

The two staircases interlock into a solid rectangle with no gaps and no overlaps. The rectangle is (n) rows tall and (n + 1) columns wide, so it holds (n(n+1)) dots, and half of them are the original staircase:

This is worth keeping in your head because it explains the shape of the answer. The (n + 1) is not a fudge factor, it is the width of the rectangle: each row of the staircase is one dot shorter than the row of gaps above it, so the two copies fit together offset by one.

Pairing and the staircase both show why the formula is true. Induction shows that it is true, mechanically, and it is the proof that generalizes to statements with no pretty picture behind them.

Base case. For (n = 1), the left side is 1 and the right side is (\frac{1 \cdot 2}{2} = 1). So (P(1)) holds.

Inductive step. Assume (P(n)) holds for some (n \ge 1). Then for (n + 1):

Substitute the inductive hypothesis for the bracketed sum:

Put both terms over a common denominator:

which is exactly the formula with (n) replaced by (n + 1). So (P(n) \Rightarrow P(n+1)), and since (P(1)) holds, (P(n)) holds for every positive integer (n).

The catch with induction is that you have to already know the answer to verify it. It confirms a guess, it does not produce one. The next proof does.

This is the one worth remembering, because it is a method rather than a trick.

Start from the difference of consecutive squares:

Sum both sides for (k = 1) to (n). On the left, almost everything cancels: the (+,(k+1)^2) from one term is destroyed by the (-,k^2) of the next.

The (+2^2) in the first bracket cancels the (-2^2) in the second, the (+3^2) cancels the (-3^2), and so on all the way along. Only the outermost terms survive:

That collapsing is what “telescoping” means. Now sum the right-hand side of the identity instead:

The two totals have to agree, since they are sums of the same terms:

Notice what happened: nowhere did we need to know the answer in advance. The formula fell out. And the method keeps working. Start from ((k+1)^3 - k^3 = 3k^2 + 3k + 1) and the same telescoping argument gives you the sum of the first (n) squares, using the sum of the first (n) integers that we just derived. Start from fourth powers and you get the sum of cubes. Each result bootstraps the next.

The closed form turns a loop into three arithmetic operations:

function sumTo(n) { return n * (n + 1) / 2; }

That is (O(1)) instead of (O(n)), which stops mattering as an optimization at small (n) and starts mattering a lot when this sits inside another loop, or when (n) is user-supplied and large.

It looks like the / 2 should be a rounding hazard, but it never is. Of any two consecutive integers (n) and (n + 1), exactly one is even, so their product is always even and the halving is exact. In a language with integer division, n * (n + 1) / 2 needs no rounding, no floor, and no epsilon.

The real hazard is the multiplication, and it is easy to miss because it strikes in a window where the answer is perfectly representable.

Take 32-bit signed integers, which top out at 2147483647:

So for every (n) from 46341 to 65535, the answer fits comfortably in the return type but the naive expression overflows on the way there. In C, signed overflow is undefined behavior, so the compiler is free to do something worse than return a wrong number.

The fix is to divide before multiplying, taking care to divide the factor that is actually even:

uint32_t sum_to(uint32_t n) { return (n % 2 == 0) ? (n / 2) * (n + 1) : n * ((n + 1) / 2); }

Now the largest intermediate value is roughly the result itself, and the full range up to 65535 works without reaching for a wider type. If you do have a wider type available, widening the accumulator is simpler and usually the better call:

uint64_t sum_to(uint32_t n) { return (uint64_t)n * (n + 1) / 2; }

In JavaScript the equivalent boundary is Number.MAX_SAFE_INTEGER ((2^{53} - 1)). Past (n \approx 1.34 \times 10^8) the product (n(n+1)) exceeds it and the result silently stops being exact, with no error and no wraparound to warn you. Use BigInt if you need to go further.

Once you recognize the shape (n(n+1)/2), it starts appearing in places that have nothing to do with adding up sequences.

Counting pairs. The number of ways to choose 2 items from (n) is

which is the sum of the first (n - 1) integers. If everyone in a room of (n) people shakes hands with everyone else, that is how many handshakes happen. Item 1 shakes (n - 1) hands, item 2 has (n - 2) new hands left to shake, and so on down to 1.

Loop counts. The classic nested loop that skips already-visited pairs runs its body (n(n-1)/2) times, not (n^2) times:

for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // runs n(n-1)/2 times } }

It is still (O(n^2)), but the constant factor of one half is real, and it is why halving the work of a broad-phase collision check or a distance matrix is worth doing.

Triangular array indexing. If you pack the lower triangle of an (n \times n) matrix into a flat array to avoid storing the redundant half of a symmetric matrix, the offset of element ((i, j)) with (j < i) is

because rows 0 through (i - 1) occupy (0 + 1 + \cdots + (i-1)) slots ahead of it.

Partial ranges. To sum from (a) to (b) rather than from 1, subtract the part you do not want:

Any arithmetic series. The pairing proof never used the fact that the step size was 1. For a sequence with constant spacing, first term (a_1) and last term (a_n), the same forwards-plus-backwards argument gives

which reads as “the number of terms times the average of the first and last.” The formula for (1 + 2 + \cdots + n) is just that with (a_1 = 1) and (a_n = n).

If you enjoyed this post or found the content helpful, I’d greatly appreciate your support! You can contribute via GitHub Sponsors to help me continue creating tutorials, demos, and open-source experiments. Every contribution, no matter the size, makes a difference and helps keep projects like this alive. Thank you!