Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This an important example of a finite integral, a good tutorial here: stanford.edu/~dgleich/publications/finite-calculus.pdf –  anon Aug 12 '10 at 19:46
3  
Note that we do not define this sum to be (x+1)x/2, we prove it to be so. It is a very useful formula. You could check out en.wikipedia.org/wiki/Triangle_number, which unfortunately, does not prove the formula you cite. –  Ross Millikan Apr 21 '11 at 22:14
    
:) My thinking was imperative, and yours declarative. –  user9912 Apr 21 '11 at 22:20
1  
Although we already have three proofs of this here, I think it would be really interesting if we amassed more (perhaps excluding the typical intro-to-induction styled proof). –  mixedmath Apr 22 '11 at 1:15

22 Answers 22

up vote 39 down vote accepted

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

share|improve this answer
    
Well, you lost me at "each term is n+1...". As far as I can see, if you add the two equations term by term it will be: n+n + (n-1)+(n-1) + ... + 2+2 + 1+1. How did you get (n+1) + (n+1) + ... + (n+1)? –  b1_ Aug 12 '10 at 18:27
8  
I got it! It's 2S = (1+2+...+(n-1)+n) + (n+(n-1)+...+2+1) - so you write one backwards, then match up each term. 2S = (1+n) + (2+n-1)+...+(n-1+2)+n+1, and so 2S=(n+1)+(n+1)+...+(n+1)+(n+1) etc –  b1_ Aug 12 '10 at 19:04
5  
This trick is usually attributed to Gauss (when he was a schoolboy... though it's unclear if the story is true or not). –  Fixee Feb 27 '11 at 15:17

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.

alt text

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:

  1. there are a total of 1 + 2 + ... + n yellow discs;
  2. every yellow disc corresponds to a unique pair of blue discs, and vice versa;
  3. there are ${n+1 \choose 2} = \frac 12 n(n+1)$ such pairs.
share|improve this answer
1  
great proof!!!! –  anon Aug 12 '10 at 21:22
1  
Maybe I lack imagination, but to me it's clearer to just make a square of yellow discs ($n^2$ of them), duplicate the diagonal ($n^2+n$), then cut in half to get the answer ($(n^2+n)/2$). This is how Knuth does this (and much more intricate) summations in "Concrete Mathematics." –  Fixee Feb 27 '11 at 15:27
2  
@Fixee: I don't know why you're comparing them; this is an entirely different proof. Unlike the other proof (also good), this doesn't require computing areas, cutting, or duplicating -- in fact this doesn't even involve the number $n(n+1)/2$ directly; what this gives is a proof that $1 + 2 + \dots + n = \binom{n+1}{2}$, and it so happens that the latter is $n(n+1)/2$. It's a bijection proof, rather than an area proof (vaguely speaking). –  ShreevatsaR Nov 25 '11 at 6:13
1  
@Vaughn Climenhaga - is there an analog of this in three dimensions and higher? –  Vincent Tjeng Apr 1 '13 at 9:43

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: enter image description here

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.

share|improve this answer
2  
I came up with the first proof by myself a long time ago :). It was an awesome moment where the concept of "area" was redefined. –  Jacob Apr 22 '11 at 1:50
1  
(+1) The first answer is good –  Hee Kwon Lee Feb 1 at 13:41

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

share|improve this answer
3  
Legend has it that Gauss used this method to find the sum of all numbers from 1 to 100 without actually summing them. –  lhf Apr 21 '11 at 22:43
3  
In class, I think. A teacher set him in a corner because he was misbehaving (apparently having already finished that day's work), and told him to add these numbers. Almost immediately, Gauss went to play because he was done - and when the teacher got angry it took her nearly 10 minutes to verify that his answer was correct! Or at least, that's how the legend I heard went. –  mixedmath Apr 21 '11 at 22:46
    
@mixedmath, Gauss's Day of Reckoning‌​, which was cited in wikipedia, discusses the legend. –  lhf Apr 21 '11 at 23:01

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

share|improve this answer

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?

share|improve this answer

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:

Each yellow dot corresponds to some pair of the n+1 dots

share|improve this answer
1  
@Mixedmath: No he means something quite different. A picture can be found in this MO-topic mathoverflow.net/questions/8846/proofs-without-words/8847#8847 –  Myself Apr 22 '11 at 0:39
    
This is a beautiful proof and doesn't seem to be getting enough appreciation, so I added the image from the MO answer to make it clearer. Feel free to remove the image if you don't want it. –  ShreevatsaR Nov 25 '11 at 5:55
    
@ShreevatsaR: That image is to powerful! –  String Sep 25 at 10:22

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 \,.$$

share|improve this answer
    
Note that the second idea is useful for generalization in that we can find the sums of any powers is we know the sums of the powers less than. It can take a lot of work but using this method, you would be able to find 1^10 + 2^2 + ... + n^10 without too much work... –  galois Sep 18 '11 at 15:07

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.

share|improve this answer
1  
Holy crap! I don't speak mathematics but thx anyway. –  b1_ Aug 12 '10 at 19:44

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

share|improve this answer
    
Here is a link to the question on our provisional faq. –  Larry Wang Aug 12 '10 at 22:30
1  
Here's the only pic I could find that shows the visual proof you describe: aplcenmp.apl.jhu.edu/Classes/605202/felikson/lectures/L2/… –  b1_ Aug 13 '10 at 2:33

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

share|improve this answer

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.

share|improve this answer
1  
Yep, that's it, write one backwards. I read this post but it didn't click - I guess I needed to write it out to see it. Thx –  b1_ Aug 12 '10 at 19:43

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

share|improve this answer

My favourite proof of this fact involves counting the edges of the complete graph $K_n$ in two different ways.

The complete graph K_9

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

share|improve this answer
    
You can easely explain this proof without graph theory... $n+1$ people went to a party, and everyone shakes hands with everyone else... How many handshakes were there? :) –  N. S. Sep 29 '12 at 14:03

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.

share|improve this answer
    
see here math.stackexchange.com/a/18989/11260 –  Peter Sheldrick Jun 14 '13 at 23:54

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

share|improve this answer

$\dfrac{k+1}2-\dfrac{k-1}2=1 \implies\dfrac{k(k+1)}2-\dfrac{(k-1)k}2=k$

$\implies \sum_{k=1}^n\Bigg(\dfrac{k(k+1)}2-\dfrac{(k-1)k}2\Bigg)=\sum_{k=1}^nk\implies\dfrac{n(n+1)}2-\dfrac{1(1-1)}2=\sum_{k=1}^nk$

$\implies\sum_{k=1}^nk=\dfrac{n(n+1)}2$

share|improve this answer

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

share|improve this answer
2  
But this is not a proof. This is an explanation. –  Asaf Karagila Sep 29 '12 at 12:00
    
@user929404: As Asaf points out, this is not a proof. You say that these proofs seem very complicated, but Joe's accepted answer for example uses the exact same idea as your explanation, but does so in a rigorous way which makes it a proof. Sometimes it is difficult to see the idea behind a proof, but it is also not enough to just give the idea; we need proof to be sure that our ideas actually work. –  Michael Albanese Sep 30 '12 at 4:21
    
This seems like a valid proof to me, at least when $n$ is even. (When $n$ is odd, you do need to say that you have $(n-1)/2$ pairs that sum to $(n+1)$, together with an additional term of $(n+1)/2$.) –  Jesse Madnick Dec 17 '12 at 19:41

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}.$$

share|improve this answer

$$\sum_{i=0}^ni-\sum_{i=0}^{n-1}i=S_1(n)-S_1(n-1)=n,$$ so that $S_1(n)$ must be a polynomial of the second degree in $n$. By the method of undeterminate coefficients, noting that there is no constant term as $S_1(0)=0$: $$S_1(n)-S_1(n-1)=n=(an^2+bn)-(a(n-1)^2+b(n-1))=\\=2an+b-a,$$ and by identification $$a=b=\frac12.$$ $$S_1(n)=\frac{n^2+n}2.$$ Let us generalize to the sum of squares, $$S_2(n)-S_2(n-1)=n^2=(an^3+bn^2+cn)-(a(n-1)^3+b(n-1)^2+c(n-1))=\\=3an^2+(-3a+2b)n+a-b+c,$$ giving $$a=\frac13,b=\frac12,c=\frac16.$$ $$S_2(n)=\frac{2n^3+3n^2+n}6.$$ For any power, you get a triangular system of equations where you recognize a part of Pascal's triangle, with alternating signs, as in the sum of cubes: $$S_3(n)-S_3(n-1)=n^3=4an^3+(-6a+3b)n^2+(4a-3b+2c)n+(-a+b-c+d),$$ $$\color{blue}{4}a=1\\-\color{blue}{6}a+\color{blue}{3}b=0\\\color{blue}{4}a-\color{blue}{3}b+\color{blue}{2}c=0\\-\color{blue}{1}a\ +\color{blue}{1}b-\color{blue}{1}c+\color{blue}{1}d=0,$$ giving $$a=\frac14,b=\frac12,c=\frac14,d=0.$$ $$S_3(n)=\frac{n^4+2n^3+n^2}4.$$

share|improve this answer
    
You can also retrieve the polynomial by Lagrange interpolation with $(0,0), (1,1),(2,3)$: $$S_1(n)=0\frac{(n-1)(n-2)}{(1-0)(2-0)}+1\frac{(n-0)(n-2)}{(1-0)(1-2)}+3\frac{(n‌​-0)(n-1)}{(2-0)(2-1)},$$ but this leads to much longer calculation. –  Yves Daoust Jul 26 at 10:22

enter image description here

Above is an image representing Pascals Triangle. What I want to draw attention to is the hockey stick formation, particularly, the blue hockey stick. Notice how the entries in the stick of the blue hockey stick are in arithmetic progression, and that the entry in the blade represents the sum of the entries in the stick.

To prove this inductively we have as a bootstrap condition

$$1=\frac{1(1+1)}{2}=\binom{1+1}{2} = \sum\limits_{i=1}^1\binom{i}{1}=1$$

and for the general case

$$\begin{array}{lll} \sum\limits_{i=1}^{n+1}&=&(n+1)+\sum\limits_{i=1}^{n}i\\ &=&\binom{n+1}{1}+\binom{n+1}{2}\\ &=&\binom{n+2}{2}\\ &=&\binom{(n+1)+1}{2}\\ &=&\frac{(n+1)((n+1)+1)}{2} \end{array}$$

Of course, we assumed that $\binom{n}{k}+\binom{n}{k+1} = \binom{n+1}{k+1}$ holds. $$\begin{array}{lll} \binom{n}{k}+\binom{n}{k+1}&=&\frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-(k+1))!}\\ &=&\frac{n!(k+1)}{k!(k+1)(n-k)!} + \frac{n!(n-k)}{(k+1)!(n-(k+1))!(n-k)}\\ &=&\frac{n!k+n!+n!n-n!k}{(k+1)!(n-k)!}\\ &=&\frac{n!+n!n}{(k+1)!((n+1)-(k+1))!}\\ &=&\frac{n!(n+1)}{(k+1)!((n+1)-(k+1))!}\\ &=&\frac{(n+1)!}{(k+1)!((n+1)-(k+1))!}\\ &=&\binom{n+1}{k+1}\\ \end{array}$$

share|improve this answer

Gathering as many proofs as we can? Write the series recursively:

$$S(n) = S(n - 1) + n \tag{1}$$

Substitute $n \to n+1$ :

$$S(n + 1) = S(n) + n + 1\tag{2}$$

Equation (2) subtract Equation (1):

$$S(n+1) - S(n) = S(n) + 1 - S(n - 1) \tag{3}$$

And write it up:

$$\begin{cases} S(n+1) &= 2S(n) -S(n-1) + 1 \\ S(n) &= S(n) \end{cases} \tag{4}$$

Which can now be written in matrix form:

$$ \begin{bmatrix} S(n+1) \\ S(n) \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} S(n) \\ S(n-1) \end{bmatrix} + \begin{bmatrix} 1 \\ 0 \end{bmatrix} \tag{5}$$

And then converting the affine equation (5) to the linear equation (6):

$$ \begin{bmatrix} S(n+1) \\ S(n+0) \\ 1\end{bmatrix} = \begin{bmatrix} 2 & -1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} S(n) \\ S(n-1) \\ 1\end{bmatrix} \tag{6}$$

And closing the equation:

$$ \begin{bmatrix} S(n+1) \\ S(n) \\ 1\end{bmatrix} = \begin{bmatrix} 2 & -1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^n \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \tag{6}$$

Then finding the Jordan form of the 3x3 matrix:

$$\begin{align} \begin{bmatrix} S(n+1) \\ S(n) \\ 1\end{bmatrix} &= \left(\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^{-1}\right)^n \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix}^n \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^{-1} \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 1 & \binom{n}{1} & \binom{n-1}{2} \\ 0 & 1 & \binom{n}{1} \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 1 & -1 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} S(1) \\ S(0) \\ 1\end{bmatrix} \end{align} \tag{7}$$

And multiplying the matrices out:

$$\begin{bmatrix} S(n+1) \\ S(n) \\ 1\end{bmatrix} = \begin{bmatrix} \frac{ (2n+2)S(1) - 2nS(0) + {n}^{2} + n}{2} \\ \frac{ 2nS(1) + (2 - 2n)S(0)+{n}^{2}-n}{2} \\ 1 \end{bmatrix} \tag{8}$$

And given that $S(0) = 0$ and $S(1) = 1$, we get that:

$$S(n) = \frac{n^2 + n}{2} \tag{9}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.