|
Apparently $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$. How? What's the proof? Or maybe it is self apparent just looking at the above? Does this problem have a name and maybe a presence on the net? And what is this math called so I can add the right tags. Thx if you can help. Edit: This problem is know as "The sum of the first $n$ positive integers". Do a search. |
|||||||||||||
|
|
Let $S = 1 + 2 + ... + (n-1) + n.$ Write it backwards: $S = n + (n-1) + ... + 2 + 1.$ Add the two equations, term by term; each term is $n+1,$ so $2S = (n+1) + (n+1) + ... + (n+1) = n(n+1).$ Divide by 2: $S = n(n+1)/2$. |
|||||||||||
|
|
My favourite proof is the one given here on MathOverflow. I'm copying the picture here for easy reference, but full credit goes to Mariano Suárez-Alvarez for this answer.
Takes a little bit of looking at it to see what's going on, but it's nice once you get it. Observe that if there are n rows of yellow discs, then:
|
|||||||||||||
|
|
What a big sum! This is one of those questions that have dozens of proofs because of their utility and instructional use. I present my two favorite proofs: one because of its simplicity, and one because I came up with it on my own (that is, before seeing others do it - it's known). The first involves the above picture: In short, note that we want to know how many boxes are in the outlined region, as the first column has 1 box, the second 2, and so on (1 + 2 + ... + n). One way to count this quickly is to take another copy of this section and attach it below, making a $n*(n+1)$ box that has exactly twice as many squares as we actually want. But there are $n*(n+1)$ little squares in this area, so our sum is half that: $$ 1 + 2 + ... + n = \dfrac{n(n+1)}{2} $$. Second proof, same as the first but a little bit harder and a little bit worse: Let us take for granted the finite geometric sum $1 + x + x^2 + ... + x^n = \dfrac{x^{n+1} - 1}{x-1}$ (If you are unfamiliar with this, comment and I'll direct you to a proof). This is a polynomial - so let's differentiate it. We get $$ 1 + 2x + 3x^2 + ... + nx^{n-1} = \dfrac{ (n+1)x^n (x-1) - x^{n+1} + 1}{ (x-1)^2 }$$ Taking the limit as x approaches 1, we get $$ lim_{x \to 1} \dfrac{ (n+1)x^n (x-1) - x^{n+1} + 1}{ (x-1)^2} = \dfrac{ (n+1) [ (n+1)x^n - nx^{n-1} ] - (n+1)x^n }{2(x-1)} = $$ $$ lim_{x \to 1} \dfrac{ (n+1)[(n+1)(n)x^{n-1} - n(n-1)x^{n-2}] - (n+1)(n)x^{n-1} } {2}$$ where we used two applications of l'Hopital above. This limit exists, and plugging in x = 1 we see that we get $$ \dfrac{1}{2} * (n+1)(n) [ (n+1) - (n-1) - 1] = \dfrac{ (n)(n+1)}{2}$$. And that concludes the second proof. |
|||||
|
|
For example, $$X = 1+2+3+4+5+6$$ Then twice $X$ is $$2X = (1+2+3+4+5+6) + (1+2+3+4+5+6)$$ which we can rearrange as $$2X = (1+2+3+4+5+6) + (6+5+4+3+2+1)$$ and add term by term to get $$2X = (1+6)+(2+5)+(3+4)+(4+3)+(5+2)+(6+1)$$ to get $$2X = 7+7+7+7+7+7 = 6*7 = 42$$ |
|||||||||||
|
|
How many ways are there to choose a $2$-element subset out of an $n$-element set? On the one hand, you can choose the first element of the set in $n$ ways, then the second element of the set in $n-1$ ways, then divide by $2$ because it doesn't matter which you choose first and which you choose second. This gives $\frac{n(n-1)}{2}$ ways. On the other hand, suppose the $n$ elements are $1, 2, 3, ... n$, and suppose the larger of the two elements you choose is $j$. Then for every $j$ between $2$ and $n$ there are $j-1$ possible choices of the smaller of the two elements, which can be any of $1, 2, ... j-1$. This gives $1 + 2 + ... + (n-1)$ ways. Since the two expressions above count the same thing, they must be equal. This is known as the principle of double counting, and it is one of a combinatorialist's favorite weapons. A generalization of this argument allows one to deduce the sum of the first $n$ squares, cubes, fourth powers... |
|||
|
|
|
Once you have a formula like this, you can prove it by induction. But that begs the question as to how you get such a formula. In this case you might ask: (a) what's the "average" term? and (b) how many terms are there? |
|||
|
|
|
Draw a triangular pyramid of base $n+1$. We get a unique coordinate for any of the $\sum_{i=1}^ni$ elements of the pyramid not in the bottom row by choosing two of the elements in the bottom row of $n+1$. This gives a bijection from the $\binom{n+1}{2}$ coordinate pairs to the $\sum_{i=1}^ni$ elements of the pyramid not in the bottom row. Image from Mariano Suárez-Alvarez's answer on Math Overflow:
|
|||||||
|
|
HINT Pair each summand $k$ with it's "reflection" $n+1-k$. This is simply a discrete analog of the method of computing the area of the triangle under the diagonal of a square by reflecting a subtriangle through the midpoint of the diagonal to form an $n$ by $n/2$ rectangle. Like the analogous proof of Wilson's theorem, the method exploits the existence of a nontrivial symmetry. In Wilson's theorem we exploit the symmetry $n \mapsto n^{-1}$ which exists due to the fact that ${\mathbb F}_p^*$ forms a group. Here we exploit a reflection through a line - a symmetry that exists due to the linear nature of the problem (which doesn't work for nonlinear sums, e.g. $\sum n^2$). Symmetries often lead to elegant proofs. One should always look for innate symmetries when first pondering problems. Generally there are (Galois) theories and algorithms for summation in closed form, in analogy to the differential case (Ritt, Kolchin, Risch et al.). A very nice motivated introduction can be found in the introductory chapter of Carsten Schneider's thesis Symbolic Summation in Difference Fields. |
|||||
|
|
Another "picture proof" I just thought of... but without a picture, since I can't draw: Suppose you want to add up all the integers from 1 to n. Then draw n rows on a board, put 1 unit in the first row, 2 in the second, and so on. If you draw a right triangle of height and length n to try and contain this shape, you will cut off half of each unit on the diagonal. So let's add all of these up; you have n^2/2 units inside the triangle, and you have n/2 unites cut off on the diagonal (there are n squares on the diagonal, and half of each one is cut off). Adding these gives n^2/2 + n/2 = n(n+1)/2. If you draw it out it makes more sense, and I think it's geometrically a bit more straightforward than the other picture proof. (Side note: I have no idea how to write math on this site... I'll go consult the meta, I'm sure there's something there about it.) |
|||||||
|
|
Basically same proof as Yoyo's, just purely combinatorial (no picture needed): How many ways can we chose two distinct numbers between $1$ and $n+1$? We pick first the largest, which is of the form $i+1$ for some $1 \leq i \leq n$, and then we have exactly $i$ distinct choices for the smallest one. Thus we have $\sum_{i=1}^n i$ choices. Here is another idea: Using $(i+1)^2-i^2=2i+1$ we get a telescopic sum: $$ \sum_{i=1}^n 2i+1 = \sum_{i=1}^n (i+1)^2-i^2 = (n+1)^2-1=n^2+2n \,.$$ Then $$n^2+2n= 2[\sum_{i=1}^n i] +n \,.$$ |
||||
|
|
The most general case of this is called an arithmetic progression or (finite) arithmetic series. There are many, many, many proofs. An easy one: write all the summands in a row; write them again just below, but from right to left now (so $1$ is under $n$, $2$ is under $n-1$, etc). Add them up, and figure out how it relates to the quantity you are looking for. |
|||||
|
|
Here is an easy way to visualize it: Draw a rectangular grid with a height of $n$ squares and width of $n+1$ squares. Obviously it has $n(n+1)$ squares in it. In the first row, color the leftmost square red and the other $n$ squares blue; in the second row, color the leftmost $2$ squares red and the other $n-1$ squares blue; and so forth (in the last row, there will be $n$ red squares and one blue square). Clearly, there are $\sum_{i=1}^n i$ red squares and the same number of blue squares. Adding the red and blue squares together, we get $2 \sum_{i=1}^n i = n(n+1)$, or $\sum_{i=1}^n i = n(n+1)/2$. |
|||
|
|
|
My favourite proof of this fact involves counting the edges of the complete graph $K_n$ in two different ways.
On the one hand, any vertex, $v_1$ say, is connected to $n-1$ other vertices, thus contributing $n-1$ edges. Moving clockwise, the next vertex $v_2$ contributes $n-2$ edges (not counting the edge connecting $v_1$ and $v_2$), $v_3$ adds $n-3$ edges, ... , $v_{n-1}$ contributes 1 edge and $v_n$ adds no new edges. Thus the total number of edges in the complete graph $K_n$ is: $$E = \sum\limits_{i=1}^{n-1} i$$ But clearly, any edge connects two vertices, so the number of edges is the number of ways to choose two distinct elements from the set $\{1,...,n\}$ and hence: $$E = \sum\limits_{i=1}^{n-1} i = \binom{n}{2} = \frac{n(n-1)}{2}$$ |
|||
|
|
This is a special case of all the formulas $$1^p+...+n^p=\frac{B_{p+1}(n+1)-B_{p+1}(0)}{p+1}$$ where $B_k(x)$ is the $k$-th Bernoulli polynomial. Provable with the Euler–Maclaurin formula or something more basic. |
|||
|
|
|
Here are two ways to calculate this sum. First is by symmetry of another sum: $\begin{aligned} \displaystyle & \sum_{0 \le k \le n}k^2 = \sum_{0 \le k \le n}(n-k)^2 = n^2\sum_{0 \le k \le n}-2n\sum_{0 \le k \le n}k+\sum_{0 \le k \le n}k^2 \\& \implies 2n\sum_{0 \le k \le n}k = n^2(n+1) \implies \sum_{0 \le k \le n}k = \frac{1}{2}n(n+1).\end{aligned}$ The second is writing it as double sum and switching the order of summation: $\begin{aligned}\displaystyle & \begin{aligned}\sum_{1 \le k \le n}k & = \sum_{1 \le k \le n}~\sum_{1 \le r \le k} = \sum_{1 \le r \le n} ~\sum_{r \le k \le n} = \sum_{1 \le r \le n}\bigg(\sum_{1 \le k \le n}-\sum_{1 \le k \le r-1}\bigg) \\& =\sum_{1 \le r \le n}\bigg(n-r+1\bigg) = n\sum_{1 \le k \le n}-\sum_{1 \le k \le n}k+\sum_{1 \le k \le n}\end{aligned} \\& \implies 2\sum_{1 \le k \le n}k = n^2+n \implies \sum_{1 \le k \le n}k = \frac{1}{2}n(n+1), ~ \mathbb{Q. E. D.} \end{aligned}$ Note I started using k back on the third line for convenience because r is just a dummy vairable at this point, and our sum no longer depends on k. Note that the first trick can easily be generalised: $\begin{aligned} & \hspace{0.5in}\begin{aligned}\displaystyle \sum_{0 \le k \le n}k^{2p} &= \sum_{0 \le k \le n}(n-k)^{2p} \\& = \sum_{0 \le k \le n}~\sum_{0 \le r \le 2p}\binom{2p}{r}n^r(-1)^{2p-r}k^{2p-r}\\& = \sum_{0 \le k \le n}k^{2p}-2pn\sum_{0 \le k \le n}k^{2p-1}+\sum_{0 \le k \le n}~\sum_{2 \le r \le 2p}\binom{2p}{r}n^r(-1)^{2p-r}k^{2p-r} \end{aligned} \\& \implies \sum_{0 \le k \le n}k^{2p-1} = \frac{1}{2pn}\sum_{0 \le k \le n}~\sum_{2 \le r \le 2p}\binom{2p}{r}n^r(-1)^{2p-r}k^{2p-r}. \end{aligned}$ |
|||
|
|
|
Look at $$1 + 2 + ... + (n-1) + n$$ Now, if we invert this we get $$n + (n-1) + ... + 2 + 1$$ When adding up those two series, you'll get $$(1+n) + (2+n-1) + ... + (n-1 +2) + (n+1)$$ Which is clearly just $$n(n+1)$$ So now we know that $$2 * (1 + 2 + ... + (n-1) + n) = n(n+1)$$ Therefore $$\frac{n(n+1)}{2} = 1 + 2 + ... + (n-1) + n$$ |
|||||
|
|
|
You can also prove it by induction, which is nice and easy, although it doesn't give much intuition as to why it works. It works for $1$ since $\frac{1\times 2}{2} = 1$. Let it work for $n$. $$1 + 2 + 3 + \dots + n + (n + 1) = \frac{n(n+1)}{2} + (n + 1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}.$$ Therefore, if it works for $n$, it works for $n + 1$. Hence, it works for all natural numbers. For the record, you can see this by applying the formula for the sum of an arithmetic progression (a sequence formed by constantly adding a rate to each term, in this case $1$). The formula is reached pretty much using the method outlined by Carl earlier in this post. Here it is, in all its glory: $$S_n = \frac{(a_1 + a_n) * n}{2}$$ ($a_1$ = first term, $a_n$ = last term, $n$ = number of terms being added). |
||||
|
|
|
All these proofs seem very complicated. The way I remember it is: The sequence is: 1, 2, 3, ..... (n-2), (n-1), n. Taking the last and first term, 2nd and (n-2)th term and so on, we form n/2 pairs of (n+1). So the sum of n/2 pairs of (n+1) is n/2 * (n+1) Example: 1, 2, 3, 4, 5, 6 = (1+6) + (2+5) + (3+4) = 3x7 =21 This still holds for an odd number of terms |
|||||||||
|
|
You can take the power series $$f(x)=\sum_{n=0}^\infty\left(\sum_{j=0}^{n}j\right)x^n$$ and you can check that it has a postive convergence ratio, and changing the order of the series you can deduce that $$f(x)=\frac{x}{(1-x)^3}.$$ On the other hand the taylor series for $\frac{x}{(1-x)^3}$ is precisely $$\frac{x}{(1-x)^3}=\sum_{n=0}^\infty \frac{n(n+1)}{2}x^n$$ so $$\sum_{j=0}^nj=\frac{n(n+1)}{2}.$$ |
||||
|
|
