How to find formula for recursive sequence sum?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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