Finding the Closed Form of a Recursion

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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