# 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.

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.

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:

$\begin{array}{cccccccccccccc}\hfill {S}_{n}=& 1& +& 2& +& 3& +& \dots & +& n-2& +& n-1& +& n\\ \hfill {S}_{n}=& n& +& n-1& +& n-2& +& \dots & +& 3& +& 2& +& 1\\ \hfill {2\cdot S}_{n}=& 1+n& +& 2+n-1& +& 3+n-2& +& \dots & +& n-2+3& +& n-1+2& +& n+1\\ \hfill =& n+1& +& n+1& +& n+1& +& \dots & +& n+1& +& n+1& +& n+1\end{array}$

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.

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$:

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

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

${S}_{n}={S}_{n-1}+n=\frac{\left(n-1\right)\left(n-1+1\right)}{2}+n=\frac{n\left(n+1\right)}{2}\phantom{\rule{1em}{0ex}}\text{QED}$

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

$\sum _{k\in K}^{}c{a}_{k}=c\sum _{k\in K}^{}{a}_{k}$

$\sum _{k\in K}^{}\left({a}_{k}+{b}_{k}\right)=\sum _{k\in K}^{}{a}_{k}+\sum _{k\in K}^{}{b}_{k}$

$\sum _{k\in K}^{}{a}_{k}=\sum _{p\left(k\right)\in K}^{}{a}_{p\left(k\right)}\phantom{\rule{1em}{0ex}}\text{Where p(k) is a permutation of k.}$

$\sum _{k=0}^{n}1=n+1\phantom{\rule{1em}{0ex}}\text{(trivial to prove by induction)}$

We then have:

${S}_{n}=\sum _{0\le k\le n}^{}k=\sum _{0\le n-k\le n}^{}n-k=\sum _{0\le k\le n}^{}n-k$

And we can add the first and last sum:

$2{S}_{n}=\sum _{0\le k\le n}^{}k+\sum _{0\le k\le n}^{}n-k=\sum _{0\le k\le n}^{}n=n\sum _{0\le k\le n}^{}1=n\left(n+1\right)$

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

${S}_{n}^{\text{'}}=1+2+4+\dots +n$

We then have:

${S}_{n}^{\text{'}}=\sum _{k=1}^{n}{k}^{2}=\sum _{k=2}^{n+1}{\left(k-1\right)}^{2}=\left(\sum _{k=2}^{n}{\left(k-1\right)}^{2}\right)+{n}^{2}$

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

$\sum _{k=1}^{n}{k}^{2}=\left(\sum _{k=1}^{n}{k}^{2}-2k+1\right)+{n}^{2}$

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

$2\sum _{k=1}^{n}k=n+{n}^{2}$

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

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

$\left\{\begin{array}{cc}\hfill {S}_{0}=& \alpha \hfill \\ \hfill {S}_{n}=& {S}_{n-1}+\beta +\gamma n\hfill \end{array}\right\$

This method works when the solution has the form:

${S}_{n}=A\left(n\right)\alpha +B\left(n\right)\beta +C\left(n\right)\gamma$

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

$\left\{\begin{array}{l}1=\alpha \\ 1=1+\beta +\gamma n\end{array}\right\$

$⇒A\left(n\right)=1$

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

$\left\{\begin{array}{l}0=\alpha \\ n=n-1+\beta +\gamma n\end{array}\right\$

$⇒B\left(n\right)=n$

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

$\left\{\begin{array}{l}0=\alpha \\ {n}^{2}={\left(n-1\right)}^{2}+\beta +\gamma n\end{array}\right\⇒\left\{\begin{array}{l}0=\alpha \\ {n}^{2}={n}^{2}-2n+1+\beta +\gamma n\end{array}\right\$

$⇒-B\left(n\right)+2C\left(n\right)={n}^{2}$

Which results in the general solution:

${S}_{n}=\alpha +n\beta +\frac{{n}^{2}+n}{2}\gamma$