2
$\begingroup$

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?

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

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

$\endgroup$
  • 1
    $\begingroup$ [+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. $\endgroup$ – Jean Marie Oct 11 '17 at 21:30
  • $\begingroup$ I realize now that the way the question has been modified, I don't answer the question of the OP. $\endgroup$ – Jean Marie Oct 11 '17 at 21:34
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @JeanMarie The OP wanted to solve the recurrence relation with a general method. At least this is what I understood... $\endgroup$ – Raffaele Oct 11 '17 at 9:57
  • $\begingroup$ 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. $\endgroup$ – Jean Marie Oct 11 '17 at 21:37
  • $\begingroup$ 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. $\endgroup$ – Cyriac Antony Jan 19 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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