A Linear Non-Homogeneous Recurrence Relation Problem I have a recurrence $a_n = a_{n-1} + n$.
and $a_1$ = 1
It is obvious that $$a_n = \sum_{i=1}^n i$$
But how can I get this closed form by using the linear non-homogeneous recurrence relation method?
 A: You can also increase the order of this recurrence relation.
Define $b_n=a_{n+1}-a_n$, then you get $$b_{n+1} - b_n = 1,$$ already a good thing. But it is also equivalent to writing $a_{n+2} - 2a_{n+1}+a_n =1$. We increased the order by $1$, but now our right hand side no longer depends on $n$.
Now we can go even further and introduce $c_n = b_{n+1}-b_n$. Obviously, its recurrence relation is $c_{n+1}=c_n$, which is a linear homogeneous (thus very easy to solve) relation. On the other hand, in terms of $a$ it rewrites as $$a_{n+3} - 3a_{n+2}+3a_{n+1} - a_n=0$$
(notice that it looks like a polynomial; in fact, it is a third discrete derivative of $a$).
You can apply your favorite method to solve this relation. The general solution writes
$$a_n = An^2+Bn+C, \quad A,B,C\in \Bbb R.$$
Now check the initial condition and the recurrence relation that you started with to obtain the coefficients $A$, $B$, and $C$.
This method works when your right-hand side is a polynomial in $n$.
A: I use generating function method 
Multiply by $x^n$ and sum from $n=1$ to $\infty$
You get $$\sum_{n=1}^{\infty}\, a_nx^n=\sum_{n=1}^{\infty}\, a_{n-1}x^n+\sum_{n=1}^{\infty}\, nx^n$$
Call $\sum_{n=1}^{\infty}\, a_nx^n=f(x)$ the formal series (doesn't matter if it converges or not)
we have $$\sum_{n=1}^{\infty}\, a_{n-1}x^n=x\sum_{n=1}^{\infty}\, a_{n-1}x^{n-1}=xf(x)$$
and 
$$ \sum_{n=1}^{\infty}\, nx^{n}=x\left( \sum_{n=1}^{\infty}\, x^{n}\right)'$$
we know that $$\sum_{n=1}^{\infty}\, x^{n}=\frac{1}{1-x}-1=\frac{x}{1-x}$$
therefore $$\left( \sum_{n=1}^{\infty}\, x^{n}\right)'=\frac{1}{(1-x)^2}$$
and then $$\sum_{n=1}^{\infty}\, nx^{n}=\frac{x}{(1-x)^2}$$
Merging all together we get
$$f(x)=xf(x)+\frac{x}{(1-x)^2}$$
$$f(x)=\frac{x}{(1-x)^3}$$
Developing in partial fractions
$$f(x)=\frac{1}{(1-x)^2}+\frac{1}{(1-x)^3}$$
And then in McLaurin series
$$f(x)=x + 3 x^2 + 6 x^3 + 10 x^4 + 15 x^5 + 21 x^6 + \ldots$$
whose coefficients are $1,3,6,10,15,21,\ldots$
that is $$a_n=\frac{n(n+1)}{2}$$
