Help with a recurrence relation?

24 Views Asked by At

I stumbled on this recurrence relation while looking at a kind of growth process. Unfortunately I haven't seen anything like this since high school! Is there a way to solve this?

$a_2 = 0$, and for $i=3,4,5,\dots$

$$a_i = \left(1-\frac{1}{i-1}\right)a_{i-1} + \frac{4}{(i-1)(i-2)}$$

The first few terms are $a_2=0$, $a_3=2$, $a_4=2$, $a_5=11/6$, $a_6=5/3$, $a_7=137/90$

Thanks!

1

There are 1 best solutions below

1
On BEST ANSWER

Rewrite $1-\dfrac1{i-1}$ as $\dfrac{i-2}{i-1}$ and multiply both sides by $i-1$ to get

$$(i-1)a_i=(i-2)a_{i-1}+\frac4{i-2}$$

Now let $b_i=(i-1)a_i$ to get

$$b_i=b_{i-1}+\frac4{i-2}$$

and

$$b_i=\sum_{j=3}^i\frac4{j-2}=4H_{i-2}$$

where $\displaystyle H_n:=\sum_{k=1}^n\frac1k$ are the harmonic numbers. This then gives us the solution

$$a_i=\frac{4H_{i-2}}{i-1}$$