Or search by topic
Published 2002 Revised 2008
c0 | c1 | c2 | c3 | c4 | c5 | c6 | c7 | |
---|---|---|---|---|---|---|---|---|
r1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
r2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
r3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 |
r4 | 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 |
r5 | 1 | 5 | 15 | 35 | 70 | 126 | 210 | 330 |
r6 | 1 | 6 | 21 | 56 | 126 | 252 | 462 | 792 |
r7 | 1 | 7 | 28 | 84 | 210 | 462 | 924 | 1716 |
r8 | 1 | 8 | 36 | 120 | 330 | 792 | 1716 | 3432 |
r9 | 1 | 9 | 45 | 165 | 495 | 1287 | 3003 | 6435 |
r10 | 1 | 10 | 55 | 220 | 715 | 2002 | 5005 | 11440 |
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 by3, 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 forn=1: \left[\begin{array}{c} k \\ k \end{array}\right] + \left[\begin{array}{c} k \\k \end{array}\right] Assumption: the statement is true forn=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 1s 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.
Find S_r = 1^r + 2^r + 3^r + ... + n^r where r is any fixed positive integer in terms of S_1, S_2, ... S_{r-1}.
Make a conjecture about the sum of the squares of the odd positive integers. Can you prove it?