Sum of the First n Integers

Q: Does the formula work when $n = 0$?

Yes. An empty list adds to 0, and $\frac{0 \cdot 1}{2} = 0$. The formula also works for $n = 1$, where $\frac{1 \cdot 2}{2} = 1$.

Q: How does this connect to big O?

The sum grows like $\frac{n^{2}}{2}$, so it is $O(n^{2})$. Big O drops the constant $\frac{1}{2}$ and the lower term $\frac{n}{2}$, because it keeps only the part that grows fastest.

In one sentence: This formula gives the total of the numbers 1, 2, 3 and so on up to $n$ in one quick calculation, with no adding one number at a time.

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

Read it out loud: “The sum, written with the Greek capital letter sigma, of i, for every whole number i from 1 up to n, equals n times n plus 1, divided by 2. The letter i is a counter that takes the values 1, 2, 3, up to n, and n is the last number in the list.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

The sum sign $\sum$: The capital Greek letter sigma, written $\sum$ , means add things up. Under it, $i = 1$ says where to start the counter, and the letter on top, $n$ , says where to stop. So $\sum_{i=1}^{3} i$ means $1 + 2 + 3 = 6$ . Each value of the counter $i$ gives one term in the total.
Whole numbers and counting numbers: Whole numbers are 0, 1, 2, 3 and so on, with no fractions and no negative numbers. Counting numbers, also called natural numbers, start at 1. The letter $n$ in this formula is a whole number. If $n = 0$ , the list is empty, and an empty total is 0.
Multiplying and dividing in a formula: Letters side by side mean multiply, so $n(n+1)$ means $n \times (n+1)$ . A fraction bar means divide, so $\frac{n(n+1)}{2}$ means the product divided by 2. Brackets come first. For $n = 4$ , $n + 1 = 5$ , the product is $4 \times 5 = 20$ , and half of 20 is 10, which equals $1 + 2 + 3 + 4$ .
Powers, like $n^{2}$: $n^{2}$ means $n \times n$ , read n squared. For $n = 10$ it is 100, and for $n = 100$ it is 10000. A power is repeated multiplication, and the small raised number is the exponent that says how many copies to multiply together.
Big O notation, like $O(n^{2})$: Big O is a short way to describe how the work grows as the input grows. $O(n^{2})$ means the work grows roughly like $n$ times $n$ for large $n$ , and small constants and smaller terms are ignored. So a total of $\frac{n^{2}}{2} + \frac{n}{2}$ is still $O(n^{2})$ , because the squared term grows fastest.
Loops and nested loops: A loop is a block of code that repeats again and again. A nested loop is a loop inside another loop. If an outer loop runs $i$ from 1 to $n$ , and the inner loop runs $i$ times on outer run number $i$ , the inner work adds up to $1 + 2 + \cdots + n$ in total.

What each symbol means

Symbol	Meaning
$\sum_{i=1}^{n} i$	The total of all the whole numbers from 1 up to $n$ , written out as $1 + 2 + 3 + \cdots + n$ . The three dots mean ‘and so on’. The result has no unit when the numbers count items, such as cans or steps.
$i$	The counter, a whole number label for each term. It starts at 1 and takes each value from 1 up to $n$ in turn, so the first term has $i = 1$ and the last has $i = n$ . It counts positions in the list, not amounts.
$n$	The last number in the list, a whole number that is 0 or more. For example $n = 100$ means the list runs from 1 to 100. It has no unit; it counts how many numbers are added, which is also the number of steps a plain loop would take.
$\frac{n(n+1)}{2}$	The closed form, a quick formula for the same total. Multiply $n$ by the next number, $n + 1$ , and then divide by 2. For $n = 100$ , that is $100 \times 101 = 10100$ , and half of that is 5050.

The formula piece by piece

$i$: The counter. On the first term $i = 1$ , on the second $i = 2$ , and on the last term $i = n$ . It is a label for the position of each term, and it moves one step at a time from 1 up to $n$ .
$\sum_{i=1}^{n} i$: The total of every term: the first number plus the second, and so on up to $n$ . Written out, it is $1 + 2 + 3 + \cdots + n$ , with $n$ terms in all.
$n + 1$: The number right after $n$ , one bigger than the last number in the list. For $n = 100$ , $n + 1 = 101$ . Pairing each number from the front of the list with one from the back gives this same total every time.
$n(n+1)$: The product of $n$ and the next number. Writing the list forward and backward gives two copies of the list, and this product adds up both copies, so it is double the total. For $n = 100$ it is $100 \times 101 = 10100$ .
$\frac{n(n+1)}{2}$: The double count removed. Dividing by 2 leaves one copy of the list, which is the total we want. The division is needed because each pair of numbers was counted twice in the product.
$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$: In one plain sentence: adding the whole numbers from 1 up to $n$ gives the same answer as multiplying $n$ by the next number, $n + 1$ , and then dividing the result by 2.

What the formula is doing, and why

What goes in and what comes out. You put in one whole number $n$ . You get out the total of all the whole numbers from 1 to $n$ . The sum shows up whenever a task takes one step for the first item, two for the second, and so on up to $n$ . Adding the numbers one at a time takes $n$ additions. The formula gives the same total with one multiplication and one division.

Why does it work? Write the list twice, once forward and once backward, and add the two copies column by column. The first number and the last make $1 + n$ . The second and the second to last make $2 + (n - 1)$ , which is also $n + 1$ . Every column adds to $n + 1$ . There are $n$ columns, so both copies together add to $n(n+1)$ .

Why divide by 2? The two copies together give $n(n+1)$ , and each copy is the same total. So one copy is half of $n(n+1)$ , which gives $\frac{n(n+1)}{2}$ . The result is always a whole number. The product of two numbers in a row, such as $n$ and $n+1$ , is always even, so half of it is always whole.

Why it matters for loops. The result grows like $\frac{n^{2}}{2}$ . The later terms are large and the early terms are small, so the total is about half of $n^{2}$ . A loop over $i$ from 1 to $n$ with an inner loop that runs $i$ times does $\frac{n(n+1)}{2}$ steps in all. That is about half of $n^{2}$ , so it is still $O(n^{2})$ in big O notation. The formula applies only when the inner count grows with $i$ .

An everyday picture

Think of stacking cans in a triangle. The top row has 1 can, the next row has 2 cans, and the bottom row has $n$ cans. Make a copy of the triangle, turn it upside down and fit it against the original. Together they form a rectangle that is $n$ rows tall and $n + 1$ cans wide. The rectangle holds $n(n+1)$ cans, so one triangle holds half of them, which is the formula’s $\frac{n(n+1)}{2}$ .

Worked example: Adding 1 to 100

Add the whole numbers from 1 to $n = 100$ , so the total is $1 + 2 + 3 + \cdots + 100$ . Then count the steps of a nested loop that reaches the same total, to see how this sum appears in code.

Find the next number. The formula needs $n + 1$ , the number right after $n$ . For $n = 100$ , it is $101$ . This is also the total of each matching pair in the forward and backward lists: $1 + 100 = 101$ , and $2 + 99 = 101$ .
Multiply. Multiply $n$ by $n + 1$ , which gives $100 \times 101 = 10100$ . This product counts both copies of the list, so it is twice the total we want. The number 10,100 is the full double count.
Divide by 2. Half of the double count is the total we want, because the double count holds each pair twice. Dividing gives $10100 \div 2 = 5050$ . So $1 + 2 + \cdots + 100$ equals 5,050.
Check it by adding one at a time. A computer can add the numbers from 1 to 100 one at a time, keeping a running total as it goes. It also reaches 5,050 at the end, so the slow method and the one-line formula agree.
Read the nested loop. An outer loop runs $i$ from 1 to 100. For each value of $i$ , the inner loop runs $i$ times. The inner work therefore adds up to $1 + 2 + \cdots + 100$ , which is the same 5,050 steps.
Compare with $n^{2}$ . The square $100^{2} = 10000$ would be the step count if the inner loop ran 100 times every time. The real count, 5,050, is about half of that: $\frac{5050}{10000} = 0.505$ . Since the share stays close to half, the work is still $O(n^{2})$ .

Answer: The sum of the whole numbers from 1 to 100 is 5,050. A nested loop whose inner body runs $i$ times for each $i$ up to 100 does 5,050 steps, which is about half of $100^{2}$ .

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Using $\frac{n(n-1)}{2}$ for the sum from 1 to $n$ . That formula stops one term early, at $n - 1$ . The sum up to $n$ uses $\frac{n(n+1)}{2}$ , with $n + 1$ , not $n - 1$ .
Forgetting the division by 2. The product $n(n+1)$ counts both copies of the list, so it is twice the sum. For $n = 100$ , leaving out the division gives 10,100 instead of 5,050.
Using the triangle formula for a fixed inner loop. If the inner loop always runs $n$ times, the total is $n^{2}$ , not $\frac{n(n+1)}{2}$ . The formula needs the inner count to grow with $i$ .
Expecting an exact $n^{2}$ result. The sum is $\frac{n^{2}}{2} + \frac{n}{2}$ , so the lower term $\frac{n}{2}$ is not zero. Big O drops it, but the exact count keeps it.

Where you will meet it

Counting comparisons in bubble sort, a simple sorting method. The first pass compares $n - 1$ pairs, the next pass compares one fewer, and so on, which adds up to $1 + 2 + \cdots + (n-1)$ .
Counting handshakes. In a group of $n$ people where each pair shakes hands once, there are $\frac{n(n-1)}{2}$ handshakes, which is the sum of the whole numbers from 1 to $n - 1$ .
Triangular numbers, such as the number of cans in a stacked triangle. Each total of 1 up to $n$ is called a triangular number.
Analyzing the cost of algorithms that check every pair of items in a list.

Questions people ask

Why is there a divide by 2?

Every pair of numbers gets counted twice when you write the list forward and backward. The product $n(n+1)$ holds both copies, so dividing by 2 leaves one copy, which is the total.

Does the formula work when $n = 0$?

Yes. An empty list adds to 0, and $\frac{0 \cdot 1}{2} = 0$ . The formula also works for $n = 1$ , where $\frac{1 \cdot 2}{2} = 1$ .

How does this connect to big O?

The sum grows like $\frac{n^{2}}{2}$ , so it is $O(n^{2})$ . Big O drops the constant $\frac{1}{2}$ and the lower term $\frac{n}{2}$ , because it keeps only the part that grows fastest.

Big O Notation: Big O notation is a way to say that one function never grows faster than another, once the input is big enough.
Geometric Series: A geometric series adds up a list where each term is the one before it times a fixed number, and this formula finds the whole sum in one step.
Master Theorem: The master theorem tells you how long a program takes when it cuts a problem into smaller pieces, solves each piece and joins the answers.