# Alok Menghrajani

Previously: security engineer at Square, co-author of HackLang, put the 's' in https at Facebook. Maker of CTFs.

This blog does not use any tracking cookies and does not serve any ads. Enjoy your anonymity; I have no idea who you are, where you came from, and where you are headed to. Let's dream of an Internet from times past.

Home | Contact me | Github | RSS feed | Consulting services | Tools & games

A classic problem in discete mathematics is finding the sum of the first $n$ natural numbers: $1+2+3+\dots +n$. This sum can also be written as: $\sum _{k=1}^{n}}k$

There are various ways to find the answer to this question. If you take a college level discrete mathematics class, you will learn various techniques. I'm going to give a quick overview of some of these techniques applied to this specific case.

### Method 1: matching pairs

Let's call the sum we are looking for ${S}_{n}$. The idea is to rewrite ${S}_{n}$ as the sum from $n$ to $1$ and then add both equations. Each element of the sum will nicely pair up:

Which leads to: ${S}_{n}=\frac{n\left(n+1\right)}{2}$. It is believed that Gauss discovered this method when he was just 9 years old.

### Method 2: proof by induction

If you have some intuition about the result or want to prove that Gauss found the right answer, you can prove that the result is right by induction.

Let's prove that the solution is correct for $n=1$:

And then let's prove that ${S}_{n}$ is correct if ${S}_{n-1}$ is correct:

### Method 3: formal notation

We can express the idea behind the first method above by using a formal notation. We need to use 4 properties:

We then have:

And we can add the first and last sum:

### Method 4: perturbation

Let's define the sum of the square of every number from $1$ to $n$:

We then have:

Since the last sum is 0 for $k=1$, we can write:

We can cancel the $\sum _{k=1}^{n}}{k}^{2$:

Which leads to: ${S}_{n}=\frac{n\left(n+1\right)}{2}$

### Method 5: repertoire

The repertoire method helps solve general forms of equations, e.g.:

This method works when the solution has the form:

We first set ${S}_{n}=1$:

We then set ${S}_{n}=n$:

Finally, we set ${S}_{n}={n}^{2}$:

Which results in the general solution:

### Links

- Concrete Mathematics by Ronald L. Graham, Donald E. Knuth and Oren Patashnik
- Carl Friedrich Gauss (wikipedia.org)
- The repertoire method in "Concrete Mathematics"