Finding the Closed Form of a Recursion I wanted to find the closed form of the recursion: $$a_n = \frac{1}{n+1} + \frac{n-1}{n+1} a_{n-1}$$ where $a_0 = 0$.
So far, my progress has been to multiply both sides by $\frac{n(n+1)}{2}$ which gives $$\frac{n(n+1)}{2} a_n = \frac{n}{2} + \frac{n(n-1)}{2} a_{n-1}.$$
Now, if we let $b_n = \frac{n(n+1)}{2} a_n$, the recursion becomes: $$b_n = \frac{n}{2} + b_{n-1}.$$
How do I continue on from here? I feel like I have to figure out a closed form for $b_n$ and use that to compute $a_n$, but I can't seem to figure out a way to do so.
Any help would be greatly appreciated.
 A: One can easily see that $a_0=0, a_n=\frac{1}{2}$ for $n\ge 1$ is the solution. However, the OP seems to be interested in general methods which could help solve this recurrence.
(In the following let's assume we are solving it for $n>0$ and with $a_1$ given, otherwise there won't be much more to add than what we've seen so far.)
There is one general observation that might help solve it: it is a linear (though not a homogenous) recurrence. This means that any solution $a_n$ of it will be possible to express as one particular solution (e.g. $b_n=\frac{1}{2}$) plus a solution of the corresponding homogenous recurrence ($c_n=\frac{n-1}{n+1}c_{n-1}$).
The last one is a telescoping recurrence: $c_n=\frac{n-1}{n+1}c_{n-1}=\frac{(n-1)(n-2)}{(n+1)n}c_{n-2}=\ldots=\frac{(n-1)(n-2)\cdots 1}{(n+1)n(n-1)\cdots 3}c_1=\frac{2}{(n+1)n}c_1$ - as all the other factors in the numerator and the denominator will cancel out. Thus, the solution for $a_n$ is: $$a_n=b_n+c_n=\frac{1}{2}+\frac{2}{(n+1)n}(a_1-\frac{1}{2})$$
A: It is simple afte OP's step:
$$B_n-B_{n-1}=\frac{n}{2}$$ Do telescoping
$$B_1-B_0=\frac{1}{2}$$
$$B_2-B_1=\frac{2}{2}$$
$$B_3-B_2=\frac{3}{2}$$
$$....................$$
$$B_{n-1}-B_{n-2}=\frac{n-1}{2}$$
$$B_{n}-B_{n-1}=\frac{n}{2}$$
$$\implies B_n=\frac{n}{2}+B_0$$
$$\implies B_n=\frac{n(n+1)}{4} \implies A_n=\frac{1}{2}$$
A: I think all of $a_n = \frac{1}{2}$
You can easily prove it using induction also.
$a_1 = \frac{1}{2}$
Assume $a_m = \frac{1}{2}$
To prove $a_{m+1} = \frac{1}{2}$
$a_{m+1} = \frac{1}{m+2} + \frac{m+1-1}{m+2} a_m$
$a_{m+1} = \frac{1}{m+2} + \frac{m}{m+2} \frac{1}{2}$
$a_{m+1} = \frac{1}{2}$
Since the relation is true for $n=1$ and assuming the result for $a_m$, we can prove it for $a_{m+1}$, hence the result is true by induction.
Also we can get the same from your equation,
$b_n = \frac{n}{2} +b_{n-1}$
$b_n = \frac{n}{2} + \frac{n-1}{2}+b_{n-2}$
$b_n = \frac{n}{2} +\frac{n-1}{2}+ \dots + \frac{n-k+1}{2} + b_{n-k}$
Substitute k = n
$b_n = \frac{n}{2} + \frac{n-1}{2}+b_{n-2}$
$b_n = \frac{n}{2} +\frac{n-1}{2}+ \dots + \frac{1}{2} + b_{0}$
$b_n = \frac{n}{2} + \frac{n-1}{2}+b_{n-2}$
$b_n = \frac{n + n-1 +n-2 + \dots +1}{2}+0$
$b_n = \frac{n(n+1)}{4}$
$\frac{n(n+1)}{2} a_n = \frac{n(n+1)}{4}$
$a_n =\frac{1}{2}$
