How to find formula for recursive sequence sum? I have the following sequence: 
$$a(1) = 1$$
$$a(n) = a(n-1) + n$$
For example: 
$$a(1) = 1$$
$$a(2) =3$$
$$a(3) =6$$
$$a(4) =10$$
$$a(5) =15$$
$$a(6) = 21$$
Which approach should I use in order to find the formula for the sum of elements $a(1)$ through $a(n)$?
Thanks :)
 A: $$a(1)=1$$
$$a(n)=a(n-1)+n$$
The first step is to observe the output
$$a(1)=1$$
$$a(2)=1+2$$
$$a(3)=1+2+3$$
$$a(4)=1+2+3+4$$
$$a(5)=1+2+3+4+5$$
From this we can see that
$$a(n)=1+2+3+\cdots +n$$
Hence
$$a(n)=\sum_{k=1}^n k=\frac{n(n+1)}{2}$$
And to find the sum of elements $a(1)$ through $a(n)$, we have
$$\sum_{k=1}^n a(k)=\sum_{k=1}^n \frac{k(k+1)}{2}=\frac12\left(\sum_{k=1}^n k^2+\sum_{k=1}^n k\right)$$
$$=\frac12\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right)$$
$$=\frac{n(n+1)(n+2)}{6}$$
A: These are known as the triangular numbers. You can rewrite this recurrence as $$a_n=\sum_{i=0}^n i={n+1 \choose 2}=\frac{n^2+n}{2}$$
The sum of triangular numbers yields the tetrahedral numbers who satisfy the equation $$T_n=\sum_{i=0}^\infty {n+1 \choose 2}=\frac{(n)(n+1)(n+2)}{6}$$
The derivation of this equation can be seen here
A: The equation you write is equivalent to
$$a(n)-a(n-1)=n$$
Sum both sides from $n=1$ to $x$ to find that the left hand side telescopes.
$$\sum_{n=1}^{x} (a(n)-a(n-1))= \sum_{n=1}^{x} n$$
$$a(x)-a(0)=\frac{x(x+1)}{2}$$
But $a(1)-a(0)=1-a(0)=1$ so $a(0)=0$.
Now that we have:
$$a(x)=\frac{x(x+1)}{2}$$
Then you can go from here,

*

*What if I forgot $\sum_{n=1}^{x} n^2$?

We can note that,
$$s(x)-s(x-1)=\frac{x(x+1)}{2}=\frac{1}{2}x^2+\frac{1}{2}x$$
Where $$s(x)=\sum_{n=1}^{x} a(n)$$
Through integration we guess the solution to this equation is of the form:
$$s(x)=ax^3+bx+cx+d$$
Then we plug $s(x)$ back into the equation and equate coefficients to get our final result. Of course noting the initial condition $s(2)=4$.
$$ax^3+bx^2+cx+d-(a(x-1)^3+b(x-1)^2+c(x-1)+d)=\frac{1}{2}x^2+\frac{1}{2}x$$
The algebra can be greatly simplified with Pascal's triangle..or you may skip this all if you have $\sum_{n=1}^{x} n^2$ memorized.
$$3ax^2+(2b-3a)x+(a-b+c)=\frac{1}{2}x^2+\frac{1}{2}x+0$$
$$a=\frac{1}{6} \implies b=\frac{1}{2} \implies c=\frac{1}{3}$$
Finally utilizing $s(2)=4$ we get $d=0$
$$s(x)= \frac{1}{6} x^3+\frac{1}{2} x^2+\frac{1}{3}x$$
$$=\frac{x(x+1)(x+2)}{6}$$
