# Sum of the First n Integers > 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. Page: https://formulabro.yunusemrevurgun.com/computer-science/sum-of-first-n-integers/ Category: Computer Science Published: 2026-10-22 Updated: 2026-10-22 ## Formula $$ \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 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. More notation help: https://formulabro.yunusemrevurgun.com/math-basics/ ## What each symbol means - $\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. 1. **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$. 2. **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. 3. **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. 4. **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. 5. **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. 6. **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}$. ## 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. ## Related formulas - [Big O Notation](https://formulabro.yunusemrevurgun.com/computer-science/big-o-notation/) - [Geometric Series](https://formulabro.yunusemrevurgun.com/computer-science/geometric-series/) - [Master Theorem](https://formulabro.yunusemrevurgun.com/computer-science/master-theorem/) ## Sources - [Triangular number, Wikipedia](https://en.wikipedia.org/wiki/Triangular_number) - [Summation, Wikipedia](https://en.wikipedia.org/wiki/Summation) From Formula Bro (https://formulabro.yunusemrevurgun.com/), a side project developed by yunusemrevurgun.com.