3

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.

theGrind24
  • 119
  • 1
    You are almost there. Write down what you get for $b_0, b_1, b_2, b_3$ and you should see it quickly! – Martin R Mar 14 '21 at 15:46
  • 1
    Have you seen what you get for $a_1$ and $a_2$ and $a_3$? The pattern is slightly obvious and easy to prove. You do not even need to know $a_0$. – Henry Mar 14 '21 at 15:52
  • 1
    @Henry "The pattern is slightly obvious" is an understatement. –  Mar 14 '21 at 15:57
  • @above the point was that I wanted to figure out a better way to find out the closed form rather than just a pattern. I agree that in case, it is pretty easy to see a pattern, but what if it was not so obvious? I wanted to just know a better way to do it in then. – theGrind24 Mar 14 '21 at 16:00

3 Answers3

2

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

1

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

Z Ahmed
  • 43,235
0

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

Vinanth S Bharadwaj
  • 420