# solving recurence relations

$i a_i = \left(i + 1\right) a_{i-1} + 2(i - 1)$ where $a_0 = a_1 = 0$

Solving this recurence relation.

How can I do this ? I tried to make something like

$i (a_i + 2(i-1)) = (i+1) (a_{i-1} + 2 (i-1))$ but find it kind of useless because i would actually change so I can't use a geometric sequence.

Does anyone know how to solve this recurrence relation ? Please show all of your steps. Thanks

-

Notice that if you divide $ia_i=(i+1)a_{i-1}+2(i-1)$ by $i(i+1)$, you get

$$\frac{a_i}{i+1}=\frac{a_{i-1}}i+\frac{2(i-1)}{i(i+1)}\;,$$

in which the two terms containing terms of the sequence have the same form. Let $b_i=\dfrac{a_i}{i+1}$; then $b_{i-1}=\dfrac{a_{i-1}}i$, and after you divide through by $i(i+1)$ your recurrence becomes

$$b_i=b_{i-1}+\frac{2(i-1)}{i(i+1)}\;,$$

where of course I assume that $i>0$. This means that the $b_i$’s are just a sum of fractions of the form $\dfrac{2(i-1)}{i(i+1)}$ for consecutive values of $i$. And $b_0=0$, so

\begin{align*} b_n&=b_{n-1}+\frac{2(n-1)}{n(n+1)}\\ &=b_{n-2}+\frac{2(n-2)}{(n-1)n}+\frac{2(n-1)}{n(n+1)}\\ &=b_{n-3}+\frac{2(n-3)}{(n-2)(n-1)}+\frac{2(n-2)}{(n-1)n}+\frac{2(n-1)}{n(n+1)}\\ &\;\vdots\\ &=\sum_{k=1}^n\frac{2(k-1)}{k(k+1)}\\ &=2\sum_{k=1}^n\frac{k-1}{k(k+1)}\\ &=2\left(\sum_{k=1}^n\frac1{k+1}-\sum_{k=1}^n\frac1{k(k+1)}\right)\\ &=2\left(H_{n+1}-1-\sum_{k=1}^n\left(\frac1k-\frac1{k+1}\right)\right)\\ &=2\left(H_{n+1}-1-\left(1-\frac1{n+1}\right)\right)\\ &=2\left(H_{n+1}+\frac1{n+1}-2\right)\;, \end{align*}

where $$H_n=\sum_{k=1}^n\frac1k$$ is the $n$-th harmonic number. Now recall that $a_n=(n+1)b_n$ to get the solution to the original recurrence:

\begin{align*} a_n&=(n+1)b_n\\ &=2(n+1)\left(H_{n+1}+\frac1{n+1}-2\right)\\ &=2\Big((n+1)H_{n+1}+1-2(n+1)\Big)\\ &=2\Big((n+1)H_{n+1}-2n-1\Big)\;. \end{align*}

-