# 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?

• Sum of an arithmetical progression : $n(n+1)/2$ – Jean Marie Oct 11 '17 at 8:41
• Umm... yes, that sum is correct but I just want to solve by recurrence method. – S. Plum P. Oct 11 '17 at 8:54

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

• [+1] This solution gives a general technique using finite differences (the keyword should be given to the OP), which is a heuristic method that does not assume (as I do in my solution) that the formula is already known. – Jean Marie Oct 11 '17 at 21:30
• I realize now that the way the question has been modified, I don't answer the question of the OP. – Jean Marie Oct 11 '17 at 21:34

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

• @JeanMarie The OP wanted to solve the recurrence relation with a general method. At least this is what I understood... – Raffaele Oct 11 '17 at 9:57
• Very sorry, you were on the right lane: I have realized that I had misunterpreted the answer the OP had done on one of my comments "I want a solution by recurrence" but my answer wasn't adapted to the text of the question. – Jean Marie Oct 11 '17 at 21:37
• From $f(x)=\frac{1}{(1-x)^2}+\frac{1}{(1-x)^3}$, how can one say that $a_n=\frac{n(n+1)}{2}$ ? Sorry, i don't understand how. – Cyriac Antony Jan 19 at 6:50