There are a multitude of ways to prove Gauss’s formula: some elementary, some not so much. This article’s purpose is to derive and prove the famous formula with simple combinatorics, pairing, induction, and more:

$$ \sum_{k=1}^{n}k=\frac{n(n+1)}{2} $$

Combinatorics Proof

#

The sum of the first n natural numbers is equal to the nth triangular number. Let \(T_n\) denote the nth triangular number. The triangular numbers seem to follow a straight path along Pascal’s Triangle, as shown by the bolded below.

Proving their relative position inductively is simple. It is obvious that S(1) is true, so S(n+1) follows. Being in the (\(n+2\))th row and the second position, \(T_{n+1}\) would be right below \(T_n\). Since \(T_{n+1}\) is equal to the quantity \(T_{n}+n+1\), and since any element in Pascal’s Triangle is equal to the two above it, the element next to \(T_n\) must be equal to \(n+1\), thus always generating a triangular number.

The \(n\)th triangular is in \(\binom{n+1}{2}\). Lemma 1.1 will then lead to the formula for the \(n\)th triangular.

$$ \begin{aligned} & \binom{n+1}{2} = \frac{(n+1)!}{2!(n+1-2)!}\\ & \implies \frac{(n+1)!}{2(n-1)!}\\ & \implies \frac{(n-1)!(n)(n+1)}{2(n-1)!}\\ & \implies \frac{n(n+1)}{2} & \end{aligned} $$

Gauss’s Pairing Proof

#

By pairing, it becomes easy to see how the formula works. Begin by listing the addends and then in reverse. Let \(s\) equal the total sum. Proceed by adding vertically-adjacent expressions.

$$ \begin{aligned} &1\hspace{26pt}+2\hspace{26pt}+3\hspace{26pt}+4\hspace{26pt}+5\ldots+n=s\\ &n+(n-1)+(n-2)+(n-3)+(n-4)\ldots+1=s\\ &\implies (n+1)+(n+1)+(n+1)...+(n+1)=2s\\ &\implies n(n+1)=2s\\ &\implies \frac{n(n+1)}{2}=s \end{aligned} $$

Induction Proof

#

Induction can only be used to prove; one must already assert that the formula is \(\frac{n(n+1)}{2}\).
To prove by induction, the statements S(1) and S(n+1) must hold true. Tacitly, the sum of the first number is equal to 1, which satisfies the initial condition. To complete the inductive proof, the following equation must hold true and will be shown to hold as such.

$$ \begin{aligned} & \frac{n(n+1)}{2}+n+1=\frac{(n+1)(n+2)}{2}\\ & \implies \frac{n^2+n}{2}+\frac{2n+2}{2}=\frac{n^2+3n+2}{2}\\ & \implies \frac{n^2+3n+2}{2}=\frac{n^2+3n+2}{2} \end{aligned} $$

Arithmetic Proof

#

This implies that the mean of the first \(n\) numbers is equal to \(\frac{(n+1)}{2}\), as the first term is 1 and the last is \(n\). Multiplying the mean by the amount of terms in the sequence is equal to the sum of the sequence; there are \(n\) terms in the sum of the first \(n\) numbers, so their sum is equal to \(\frac{n(n+1)}{2}\).

Quadratic Proof

#

Let \(f(n)=T_n\), where \(T_n\) is the \(n\)th triangular. We can surmise its degree by checking for the presence of a common difference.
The sequence follows: \(\{0, 1, 3, 6, 10\ldots\}\). The first differences are \(\{1, 2, 3, 4\ldots \}\). The second differences will always follow \(\{1, 1, 1, 1\ldots \}\) from the differences of consecutive numbers, so \(f(n)\) must be quadratic.

Following Lemma 7.1, the \(a\) coefficient of \(f(n)\) is \(\frac{1}{2}\), and the \(c\) coefficient is 0, so there is no constant term. To find the coefficient of \(b\), one must substitute given terms. We will use the \(5\)th term of the sequence as an example.

$$ \begin{aligned} & f(n) = \frac{n^2}{2} + bn + 0\\ & \implies 10=\frac{4^2}{2} + 4b\\ & \implies \frac{1}{2}=b\\ & \implies f(n)=\frac{n^2}{2} + \frac{n}{2}\\ & \implies f(n)=\frac{n(n+1)}{2}\\ \end{aligned} $$