S(n): The sum of the first n natural numbers

Natural numbers are the first numbers that we learn at an early age. They are represented mathematically as $\mathbb N = \{1, 2, 3, \cdots\}$. In this blog, we will look at the sum of the first $n$ natural numbers. Let’s represent this by a function $S(n) = \sum_{i=1}^n i = 1 + 2 + 3 + \cdots + n$.

$S(1) = 1$.

$S(2) = 1 + 2 = 3$.

$S(3) = 1 + 2 + 3 = 6$.

We want to find a general formula for $S(n)$. Before we start doing some calculations, let’s talk about some places where this function appears.

Applications of S(n)S(n)S(n)#

The term $S(n) = \sum_{i=1}^n i$ often appears when we are trying to compute the time complexity of different algorithms. Mostly, we can see this appearing in nested loops. Sorting algorithms, like insertion and bubble sort, are examples of this term.

Closed-form representation of S(n)S(n)S(n)#

We want to represent $S(n)$ in a closed form rather than expressing it as a summation of $n$ natural numbers. The closed-form representation can be thought of as a mathematical function, e.g., $S(n) = \frac{n(n+1)}{2}$. In fact, this is exactly what $S(n)$ is. How? This is the question we will answer in this blog. We will show that $S(n) = \frac{n(n+1)}{2}$ in five different ways. The last one is a classical proof, which is the shortest and the easiest proof among all of them. Moreover, it also has historical significance. We’ll leave the best for the end.

The method of induction#

Mathematical induction is a proof technique in which a statement like $S(n) = \frac{n(n+1)}{2}$ can be proved by performing two steps. The first step is called the base case, in which the claim for the first element is $S(1)$ is proved. The second is the inductive step, where we prove that if the claim holds for some term $S(n)$, then the claim will also hold for the next term $S(n+1).$ Going through these two steps successfully will establish the correctness of the formula.

Base case#

$S(1)$ is the sum of the first term, which means that we only have one term. This term is the number $1.$ Therefore, the correct value for $S(1)$ is $1$.

According to the proposed formula, $S(n) = \frac{n(n+1)}{2}$. If we replace the value of $n$ by $1$, we get $S(1) = \frac{1(1+1)}{2} = \frac{1(\cancel2)}{\cancel{2}} = 1$. This shows that the formula is correct for the first value, i.e., $n = 1$, which proves the base case.

Inductive step#

Here, we assume that the formula holds for $n,$ i.e., $S(n) = \frac{n(n+1)}{2}$. Our goal is to prove that the formula holds for $n+1$. In simpler terms, we want to show that $S(n+1) = \frac{(n+1)((n+1)+1)}{2}$.

We know that $S(n)$ is the sum of the first $n+1$ natural numbers.

$S(n+1) = 1 + 2 + 3 + \cdots + n + (n+1)$.

We can rewrite the above expression as:

$S(n+1) = (1 + 2 + 3 + \cdots + n) + (n+1)$.

We know that $S(n+1) = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2},$ therefore:

$S(n+1) = \frac{n(n+1)}{2} + (n+1)$

$\implies S(n+1) = \frac{n(n+1)}{2} + \frac{2(n+1)}{2}$

$\implies S(n+1) = \frac{(n+1)(n+2)}{2}$.

This completes the proof.

We have proved that $S(n) = \frac{n(n+1)}{2}$ using mathematical induction or proof by induction. Can we prove the same statement by using some simpler techniques? The answer is yes. Our next proof employs a method taught well before the mathematical induction. Let’s see what it is.

Simultaneous equations#

Let’s start with a quadratic equation for $S(n)$.

$S(n) = an^2 + bn + c$.

Finding the value of the constants $a$, $b$, and $c$ will give us the closed-form equation for $S(n)$.

Let’s put the values of $n = 1, 2, 3$ to get three equations.

$S(1) = a+b+c=1 \hspace{4em} (Eq.\space 1)$

$S(2) = 4a + 2b +c= 3\hspace{3em} (Eq.\space 2)$

$S(1) = 9a + 3b + c = 6\hspace{3em} (Eq. \space3)$

Let’s remove one of the variables.

$(Eq. \space 2-Eq. \space 1)\hspace{3em}3a + b = 2\hspace{3em} (Eq. \space 4)$

$(Eq. \space 3-Eq. \space 1)\hspace{3em}8a + 2b = 5\hspace{2.5em} (Eq. \space 5)$

Now, let’s remove another variable.

$(Eq. \space 5- \space 2\times Eq. \space 1)\hspace{3em}2a = 1\hspace{2.5em}$

$\implies a = \frac{1}{2}.$

Using the value of $a$ in $Eq. \space 4$ gives the value of $b= \frac{1}{2}$.

Using the values of $a$ and $b$ in $Eq. \space 1$ gives the value of $a=0$.

Using these values, we can see that:

$S(n) = \frac{1}{2}n^2 + \frac{1}{2}n + 0c$ $\implies S(n) = \frac{n(n+1)}{2}$.

Again, we are getting the same formula but using a different technique.

Let’s briefly describe the third method before moving on to the more interesting solutions.

Linear algebra#

The first three equations from the previous section will be used as a starting point for this method. Let’s rewrite those equations below.

$S(1) = a+b+c=1 \hspace{4em} (Eq.\space 1)$

$S(2) = 4a + 2b +c= 3\hspace{3em} (Eq.\space 2)$

$S(1) = 9a + 3b + c = 6\hspace{3em} (Eq. \space3)$

The following matrices and matrix multiplication express these three equations:

$\begin{bmatrix} 1 & 1 & 1\\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{bmatrix} \times \begin{bmatrix} a\\b\\c \end{bmatrix} = \begin{bmatrix} 1\\3\\6 \end{bmatrix}$.

If we multiply both sides by the inverse of the first matrix, we will get the values of $a$, $b$, and $c$. The inverse of a matrix can be found using the Gaussian elimination algorithm. This algorithm is known after the famous mathematician Carl Friedrich Gauss. We will hear about this name again, but for now, let’s see the inverse of this matrix.

The inverse of $\begin{bmatrix} 1 & 1 & 1\\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{bmatrix} = \begin{bmatrix} 1/2 & -1 & 1/2\\ -5/2 & 4 & -3/2 \\ 3 & -3 & 1 \end{bmatrix}$.

We get the following result if we multiply both sides with this inverse matrix:

$\begin{bmatrix} 1/2 & -1 & 1/2\\ -5/2 & 4 & -3/2 \\ 3 & -3 & 1 \end{bmatrix} \times\begin{bmatrix} 1 & 1 & 1\\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{bmatrix} \times \begin{bmatrix} a\\b\\c \end{bmatrix} = \begin{bmatrix} 1/2 & -1 & 1/2\\ -5/2 & 4 & -3/2 \\ 3 & -3 & 1 \end{bmatrix} \times\begin{bmatrix} 1\\3\\6 \end{bmatrix}$

$\implies \begin{bmatrix}a\\b\\c\end{bmatrix} = \begin{bmatrix}1/2\\1/2\\0\end{bmatrix}$.

Once more, we reach the same conclusion, the same values for the variables, and the same closed-form, i.e., $S(n) = \frac{n(n+1)}{2}$.

Number of edges of a completely connected graph#

Consider a graph with $n+1$ vertices. If every pair of this graph has an edge between them, then it is a completely connected graph. It is represented by $K_{n+1}$. Let’s see some of the completely connected graphs below.

For $n=1$, the number of edges in $K_2 = 1$.

For $n=2$, the number of edges in $K_3 = 3$.

For $n=3$, the number of edges in $K_4 = 6$.

Let’s count the number of edges of $K_{n+1}$.

The first way to count#

Let’s count the edges of each vertex one by one. The first vertex is connected to all the other $n$ vertices. We will start adding the number of edges of other vertices to this number.

The second vertex is also connected to all the other $n$ vertices, but we have already counted one of its edges—one that is formed with the first vertex. This leaves a total of $n-1$ more edges that we need to count.

For the third vertex, which, again, is connected to all the other $n$ vertices, we count only $n-2$ of its edges. This is because two of its edges have already been accounted for. These are the ones with the first two vertices.

We can see a decreasing trend here; first we get $n$, then $n-1$, and then $n-2$. This continues until we reach the end, where we add $1$ to this list.

This means the total number of edges in $K_{n+1} = n + (n-1) + (n-2) + \cdots + 1$.

By writing the same terms in increasing order, we get $K_{n+1} = 1 + 2 + 3 + \cdots + n$.

The second way to count#

In the last section, we noticed that in $K_{n+1}$, every vertex is connected to all the other $n$ vertices. This means that every vertex has $n$ edges. There are $n+1$ vertices in total. So, the total number of edges should be $n \times (n+1)$.

Here, every edge is counted twice. This is because every edge is connecting two vertices. This means that this edge is counted in the list of edges of both vertices, implying that in the previous part, we over-counted the number of edges by a factor of two. In mathematical terms, this is called double counting. To fix this, we simply need to divide the result by $2$. Therefore, the total number of edges in $K_{n+1} = \frac{n(n+1)}{2}$.

Comparing the two counting results#

In both methods, we are counting the same quantity—the total number of edges in a completely connected graph with $n+1$ vertices. Because both expressions represent the count of the same item, therefore, both of these $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$. This reproduces the same result, i.e., $S(n) = \frac{n(n+1)}{2}$.

Number of boxes in a triangle#

Let’s suppose we have $n$ piles of square blocks. In the first pile, there is only $1$ block, in the second pile, there are $2$ blocks, and so on, until the last pile, which has $n$ blocks. We want to derive a formula for the number of these blocks. From the description, we can see that the number of these blocks $=1 + 2 + 3 + \cdots + n$. Let’s call this number $S(n)$. You can see a pictorial representation of this arrangement below.

You can observe a triangle-like shape in the above image if you notice carefully. These number of blocks are also called triangular numbers. The above image represents the fifth triangular number because it contains five piles.

You can also observe that the last pile contains the maximum number of blocks. This maximum number is equal to the number of piles in the diagram. Here, it is five.

If we flip the arrangement of these blocks along the diagonal, the total number of blocks will remain unchanged. For five piles, this rearrangement can be shown in the diagram below.

Stacking these piles on each other will convert these two triangles into a rectangular structure, as shown in the diagram below.

Because we combined both piles, the total number of blocks now is $2 \times S(n)$. Moreover, it is easy to note that after this combination, there will be $n$ piles, each containing $n+1$ blocks. Therefore, the total number of blocks in the resultant rectangle $=n(n+1)$.

$\implies 2 \times S(n) = n(n+1)$

$\implies S(n) = \frac{n(n+1)}{2}$.

The above argument provides a visual proof of the underlying closed-from expression.

Triangles instead of rectangles#

The numbers under discussion are called triangular numbers. Let’s discuss another method that uses the formula to calculate the area of a triangle.

The above illustration represents the fifth triangular number. This is the same illustration that we saw earlier but with the spaces between the boxes removed. Let’s suppose that each side of these squares is of unit length, which means that this square has an area of $1$ unit. A figure corresponding to the $n^{th}$ triangular number will have a base and height of $n$ units each, and the area of such a figure will give us the value of the $n^{th}$ triangular number, i.e., $S(n)$. Let’s embed a triangle in the diagram and use the formula of the area of the triangle to derive the required formula for $S(n)$.

For the $n^{th}$ triangular number, its corresponding illustration, like the one shown above, will have a base and height of length $n.$ The area of similar triangles can be calculated by the formula $\frac{1}{2}(base \times height)$. Therefore, the area of the required triangle is $\frac{n^2}{2}.$ From the illustration above, we can see that some portion is not covered by this triangle, and we need to add some more in order to cover the whole area. It is evident that we are missing half the squares $n$ number of times, so we add this number. The final value of $S(n)= \frac{n^2}{2} + \frac{n}{2} = \frac{(n)(n+1)}{2}$.

This method also produces the exact same formula as the previous ones.

A simple method for calculation#

Now, let’s discuss the final and the most elegant argument among all of these. This method is attributed to Gauss. The story goes like this.

When Gauss was in elementary school, his teacher, who was not in the mood to teach that day, asked his students to add the first 100 natural numbers. Just as the teacher wanted, his classmates added the integers one by one. To everyone’s surprise, including the teacher, Gauss announced the answer $5050$ very quickly. Let’s understand the technique used by Gauss and then generalize it for any value of $n$.

Let’s look at the illustration above. The first number $(1)$ is paired with the last number $(100)$, and their sum is $101$. The second number $(2)$ is paired with the second-last number $(99)$, and their sum is $101$. Similarly, each of the $50$ pairs has a sum equal to the same number $(101)$. Therefore, the sum of all these numbers is $50 \times 101 = 5050$.

Generalization of the addition principle#

Let’s start with the following equation.

$S(n) = 1 + 2 + 3 + \cdots + (n-2) + (n-1) + n \hspace{3em} (Eq. \space 1)$

We want to find out a closed-form expression for $S(n)$. We know that when we add some numbers, their order is not important. This means that we can rewrite $S(n)$ by adding the same numbers but in descending order.

$S(n) = n + (n-1) + (n-2) + \cdots + 3 + 2 + 1 \hspace{3em} (Eq. \space 2)$

Now, let’s add these two equations. Let’s write them again, one over the other, so that the addition process can be described easily.

$\hspace{3em}S(n) \hspace{0.6em}= \hspace{0.5em}1 \hspace{1.4em}+ \hspace{1em}2 \hspace{1em}+ \hspace{1em}3 \hspace{1.3em}+ \cdots + (n-2) + (n-1) + \hspace{1em}n$

$\hspace{2em} + \space S(n)\hspace{0.6em} = \hspace{0.5em}n \hspace{1.55em}+ (n-1) + (n-2) + \cdots + \hspace{1em}3 \hspace{1.22em}+ \hspace{1em}2 \hspace{1.2em}+ \hspace{1em}1$

$\implies 2\times S(n) = (n+1) + (n+1)+ (n+1) + \cdots + (n+1)+ (n+1)+ (n+1)$.

Each pair adds up to $n+1$, and there are $n$ such pairs, so the total comes out to be $n(n+1)$.

$\implies 2\times S(n) = n(n+1)$

$\implies S(n) = \frac{n(n+1)}{2}$.

A different flavor of the same proof is also available in a blog explaining why vector (in C++) and arraylist (in Java) are so fast.

It is easy to observe that the method used by Gauss is simple and does not require much understanding of mathematical proofs and other problem-solving techniques. However, other techniques have their own advantages because they can be used in several different scenarios.

Concluding remarks#

As you see, there are multiple ways to achieve the same results. Some of these methods are long, some short. Some of them are boring, others very interesting. Some of them even fascinate us enough to learn more about the topic.

To learn more about counting techniques and graphs, please look at the following very interesting courses. These courses will capture your interest and guide you through the topic in an engaging and interactive way.