The Kth Sum of N Numbers

Ever since the dawn of mathematics, mathematicians have been interested in the summation of numbers. For every given series we could define a sum of that certain series. Studying sums of series, led me to some pretty nice discoveries that I'll show in this article.

One of the most basic sums is the sum of all the natural numbers up till $n$. It is widely known that this sum can be found by the formula: $$\frac{n(n+1)}{2}$$ Let's check some numbers and see if it works:

$1+2+3+4=4(4+1)/2=20/2=10$

$1+2+3+4+5+6+7+8=8(8+1)/2=72/10=36$.

This formula can be easily proven by induction (I'll leave this to the reader).

What if we take the series of numbers that are the sums of numbers up to a certain number (these are called the triangular numbers), or in other words the series:

$1$, $3$, $6$, $10$, $15$, $21$, $28$, $\ldots$ where $$a_n=\frac{n(n+1)}{2}$$ gives us the terms of this series. How would we find the sum of this series?

Let's take a look at the partial sums we get:

$1=1$

$1+3=4$

$1+3+6=10$

$1+3+6+10=20$

$1+3+6+10+15=35$

$1+3+6+10+15+21=56$

and so on. Is there any general formula for this sum? Let's take a closer look and try to find out:

$1=1$

$4=2\times 2$

$10=3\times(3+1/3)$

$20=4\times 5$

$35=5\times 7$

$56=6\times(9+1/3)$

We might try to conjecture that they are: $n\times$ (another number), but not all of them are whole numbers. We can conjecture that the ones that are not integers have fractions with a denominator of $3$. If this is true, we could multiply all of these numbers by$3$, and the fractions will disappear. Let's try it out:

$1\times 3=3=1\times 3$

$4\times 3=12=2\times 6$

$10\times 3=30=3\times 10$

$20\times 3=60=4\times 15$

$35\times 3=105=5\times 21$

$56\times 3=168=6\times 28$

In these products $1$, $2$, $3$, $4$, $5$, $6$, $\ldots$ are the integers, and $3$, $6$, $10$, $15$, $21$, $28$, $\ldots$ are the triangular numbers that we know are equal to $$\frac{n(n+1)}{2}.$$ Let's call this sum $b_n$. Each partial sum is a product of $n$ and the $(n+1)^{\textrm{th}}$ triangular number, this gives the following formula: $$3b_n=n\times\frac{(n+1)(n+2)}{2}$$ $$b_n=\frac{n(n+1)(n+2)}{6}$$ Now let's prove, by induction, that: $$1+3+6+10+15+\ldots+\frac{n(n+1)}{2}=\frac{n(n+1)(n+2)}{6}$$ First let's check if it is true when $n=1$. $$1=\frac{1(2)(3)}{6}=1$$ Assumption: the statement is true for $n=k$, a certain integer, that is: $$1+3+6+10+15+\ldots+\frac{k(k+1)}{2}+\frac{k(k+1)(k+2)}{6}$$ To prove it for $n=k+1$, let's add the next termto the LHS and to the RHS: $$1+3+6+40+15+...+\frac{k(k+1)}{2}+\frac{(k+1)(k+2)}{2} $$ $$ =\frac{k(k+1)(k+2)}{6}+\frac{(k+1)(k+2)}{2} $$ $$ =\frac{k(k+1)(k+2)+3(k+1)(k+2)}{6} $$ $$ =\frac{(k+1)(k+2)(k+3)}{6} $$ Thus proved for all $n$ by the axiom of induction.

The sums given by $b_n$ also form a series, and we can find the formula for their partial sums in a method very similar to the one described above (I'll leave the interested reader to try to find it). It turns out to be: $$\frac{n(n+1)(n+2)(n+3)}{24}$$ Some readers may realize a pattern is forming here. Let's define $a_n$ to be the first sum of numbers up till $n$, $b_n$ to be the second sum of numbers up till $n$, and so on.

So we get a general formula for the $k^{\textrm{th}}$ sum of numbers up till $n$:

$$\frac{n(n+1)(n+2)...(n+k)}{k+1}= \frac{(n+k)!}{(n-1)!(k+1)!}= \left[\begin{array}{c} n+k \\n-1 \end{array}\right] = \left[\begin{array}{c} n+k \\k+1 \end{array}\right] $$ What we actually get is that the sum can be seen as a binomial coefficient!

Let's try to prove this formula by induction: $$ \left[\begin{array}{c} k \\ k \end{array}\right] + \left[\begin{array}{c} k+1 \\k \end{array}\right] + \left[\begin{array}{c} k+2 \\k \end{array}\right] +... + \left[\begin{array}{c} n+(k-1) \\k \end{array}\right] = \left[\begin{array}{c} n+k \\ k+1 \end{array}\right] $$ Checking for$n=1$: $$ \left[\begin{array}{c} k \\ k \end{array}\right] + \left[\begin{array}{c} k \\k \end{array}\right] $$ Assumption: the statement is true for$n=m$, a certain integer, that is: $$ \left[\begin{array}{c} k \\ k \end{array}\right] + \left[\begin{array}{c} k+1 \\k \end{array}\right] + \left[\begin{array}{c} k+2 \\k \end{array}\right] +... + \left[\begin{array}{c} m+(k-1) \\k \end{array}\right] = \left[\begin{array}{c} m+k \\ k+1 \end{array}\right] $$ To prove it for $n=m+1$,let's add the next term to the RHS and the LHS: $$ \left[\begin{array}{c} k \\ k \end{array}\right] + \left[\begin{array}{c} k+1 \\k \end{array}\right] + \left[\begin{array}{c} k+2 \\k \end{array}\right] +... + \left[\begin{array}{c} m+(k-1) \\k \end{array}\right] + \left[\begin{array}{c} m+k \\ k \end{array}\right] $$

$$ = \left[\begin{array}{c} m+k \\k+1 \end{array}\right] + \left[\begin{array}{c} m+k \\ k \end{array}\right] $$

$$ = (m+k)!({\frac{1}{(k+1)!(m-1)!}} + {\frac{1}{k!m!}}) $$

$$ = (m+k)! (\frac{m+k+1}{(k+1)!m!}) $$

$$ = \frac{(m+k+1)!}{(k+1)!m!} $$

$$ = \left[\begin{array}{c} m+k+1 \\k+1 \end{array}\right] $$ Thus, it is proved.

Actually, this is a very well known binomial identity.

By placing $k=1$, $2$, $3$ $\ldots$ we can get all the formulae for all the $k^{\textrm{th}}$ sum of numbers up till $n$. Quite cool.

Actually, it is no surprise that we get a binomial coefficient to describe this kind of sums. Binomial coefficient have a strong relation with Pascal's triangle. The natural numbers are the partial sums of the $1$s in the outer line, the triangular numbers form the next line, and so on. The reader may write down Pascal's triangle and verify that this is true. To find the partial sum of all the numbers in any line, simply look at the number directly to the right of the last number to be summed, and below in the triangular array. This is exactly what we proved by induction. (More information about the connection to Pascal's triangle may be found in Martin Gardner's book Mathematical Carnival ).

The reader may want to try to find these kinds of sums for other sums of series. If you find something of interest I'm sure that I, and others as well, will be interested to hear about it.

Yatir Halevi is 18 years old, he lives in Maccabim, Israel and goes to the Maccabim-Reut High-School.