How was a factorial/gamma function obtained from solving this recurrence relation?

54 Views Asked by At

So I came up with the following recurrence relation for $m \geq 2$ and initial value $a_1 = 1$: $$a_m = m+(m+1)a_{m-1}$$

Putting this result into Wolfram Alpha yields the following closed form: $$a_m = \Gamma(m+2) - 1$$

I get how factorials/the gamma function might show up here, since for example, $a_5=5+6(4+5(3+4(2+(3*1))))$ which looks like a factorial would be involved. But I'm not sure how to go about solving it to get that explicit closed form.

2

There are 2 best solutions below

0
On BEST ANSWER

Hint: $\;$ write it as $\,a_m+1=(m+1)(a_{m-1}+1)\,$ and telescope.

0
On

Another, more general way.

Suppose $a_m =u_m+v_ma_{m-1} $ with the $u_m$ and $v_m$ known.

Let $V_m=\prod_{k=1}^m v_k $ so $V_m =v_mV_{m-1} $ or $\dfrac{v_m}{V_m} =\dfrac1{V_{m-1}} $.

Then, dividing by $V_m$,

$\begin{array}\\ \dfrac{a_m}{V_m} &=\dfrac{u_m}{V_m}+\dfrac{v_m}{V_m}a_{m-1}\\ &=\dfrac{u_m}{V_m}+\dfrac{a_{m-1}}{V_{m-1}}\\ \text{Let}\\ b_m &=\dfrac{a_m}{V_m}\\ \text{and}\\ w_m &=\dfrac{u_m}{V_m}\\ \text{Then}\\ b_m &=w_m+b_{m-1}\\ \text{or}\\ w_m &=b_m-b_{m-1}\\ \text{Summing,}\\ b_M-b_2 &=\sum_{m=2}^M (b_m-b_{m-1})\\ &=\sum_{m=2}^M w_m\\ \text{or}\\ b_M &=b_2+\sum_{m=2}^M w_m\\ \text{or}\\ \dfrac{a_M}{V_M} &=\dfrac{a_2}{V_2}+\sum_{m=2}^M w_m\\ \text{or}\\ a_M &=\dfrac{a_2V_M}{V_2}+V_M\sum_{m=2}^M \dfrac{u_m}{V_m}\\ &=a_2\prod_{k=3}^M v_k+\sum_{m=2}^M u_m\prod_{k=m+1}v_k\\ \end{array} $

If $v_k=k+1$ then $V_m=(m+1)!$ and this is where the factorial comes from.