How to Calculate the Sum of First N Natural Numbers

Problem Statement

Evaluate

$$\\x=\sum_{k=1}^{N} k \quad for \: any \: given \: N$$

Example

$$For\:N = 5,\quad \\x = \sum_{k=1}^{5} k = 15$$

Solution

Let’s break the problem into similar smaller problems and try to understand what actually is the question asking. We will try to establish a recurrence relation which solves the bigger problem by using the solution to a smaller subproblem which is already known. For instance take N = 8, then sum of the first 8 terms, i.e., sum(8) can be defined as

$$\begin{equation} \begin{aligned} sum(8) &= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 \\&= 36 \end{aligned} \tag{1} \end{equation}$$

Now let’s take N = 7 and calculate the sum of the first 7 terms,

$$\begin{equation} \begin{aligned} sum(7) &= 1+2+3+4+5+6+7\\&=28 \end{aligned} \tag{2} \end{equation}$$

Now let’s combine the results of equation (1) & (2) and see what we get,

$$\begin{aligned} sum(8) &= sum(7) + 8 \\ &=28 + 8 \\ &=36 \end{aligned}$$

It’s clear now that the sum of first 8 terms can be defined as that of first 7 terms added with the 8th term, i.e., sum(8) = sum(7) + 8. Finally let’s now take the value of N = n, i.e., some arbitrary number. Then sum(n) can be defined as

$$sum(n) = sum(n-1) + n$$

That’s it! Now we have derived a formula for summation of n terms by simply adding the sum up to (n-1) terms with the nth term itself. But wait, for every n you must have summation up to n-1. So when n = 1, what is the summation up to n-1 i.e., sum(0)? The answer is

$$sum(0) = 0$$

This is the fundamental unit of information which helps to find sum up to n terms. For instance sum(1) = sum(0) + 1 = 1. Once you have sum(1), you can easily compute sum(2) as sum(1) + 2 and so on. Now we have enough information to come up with a recurrence relation.

$$sum(n) = \begin{cases} 0 & \text{if } n = 0 \\ sum(n-1) + n& \text{if } n > 0 \end{cases}$$

The only job remaining now is to write the above recurrence relation as a recursive function. I am using C, you can go with any other language of your choice.

int sum(int n) {
    if(n < 1) {
        return 0;
    }
    return sum(n-1)+n;
}

• Time Complexity: O(n)

• Space Complexity: O(n)

🎯A challenge for readers - Come up with a recurrence relation to find n!

---

This article evaluates the summation of the first N natural numbers by establishing a recurrence relation and solving it using recursion. It explains the concept through examples, builds the recurrence relation sum(n) = sum(n-1) + n, and implements it as a recursive function in C. The solution has a time complexity of O(n) and a space complexity of O(n).