# Solve the recurrence relation: na_n = (n-4)a_{n-1} + 12n H_nna_n = (n-4)a_{n-1} + 12n H_n

I want to solve
$$na_n = (n-4)a_{n-1} + 12n H_n,\quad n\geq 5,\quad a_0=a_1=a_2=a_3=a_4=0. na_n = (n-4)a_{n-1} + 12n H_n,\quad n\geq 5,\quad a_0=a_1=a_2=a_3=a_4=0.$$

Does anyone have an idea, what could be substituted for $$a_na_n$$ to get an expression, which one could just sum up? We should use
$$\sum_{k=0}^n \binom{k}{m} H_k = \binom{n+1}{m+1} H_{n+1} – \frac{1}{m+1} \binom{n+1}{m+1} \sum_{k=0}^n \binom{k}{m} H_k = \binom{n+1}{m+1} H_{n+1} - \frac{1}{m+1} \binom{n+1}{m+1}$$
to simplify the result.

Here is a different approach: Consider the change of variable $$b_n=a_{n+4},b_n=a_{n+4},$$ so that the only initial condition is given by $$b_0=0.b_0=0.$$ Notice that the equation becomes
$$(n+5)a_{n+5}-(n+4)a_{n+4}+3a_{n+4}-12(n+5)H_{n+5}=0,(n+5)a_{n+5}-(n+4)a_{n+4}+3a_{n+4}-12(n+5)H_{n+5}=0,$$
$$(n+5)b_{n+1}-(n+4)b_{n}+3b_{n}-12(n+5)H_{n+5}=0,(n+5)b_{n+1}-(n+4)b_{n}+3b_{n}-12(n+5)H_{n+5}=0,$$
take $$f(x)=(x+4)b_xf(x)=(x+4)b_x$$ so that $$\Delta (f)=f(x+1)-f(x)=(x+5)b_{x+1}-(x+4)b_x,\Delta (f)=f(x+1)-f(x)=(x+5)b_{x+1}-(x+4)b_x,$$
so we get that $$\Delta (f(x))=\frac{-3}{x+4}f(x)+12(x+5)H_{x+5}.\Delta (f(x))=\frac{-3}{x+4}f(x)+12(x+5)H_{x+5}.$$
This looks like variation of parameters, check Remark 10.
We get then that the solution becomes
$$f(x)=\sum _{u=1}^{x-1}\left (\prod _{t=u+1}^{x-1} \left (1-\frac{3}{t+4}\right )\right )\cdot \left (12(u+5)H_{u+5}\right ),f(x)=\sum _{u=1}^{x-1}\left (\prod _{t=u+1}^{x-1} \left (1-\frac{3}{t+4}\right )\right )\cdot \left (12(u+5)H_{u+5}\right ),$$
notice that the product becomes
$$\left (\prod _{t=u+1}^{x-1} \left (1-\frac{3}{t+4}\right )\right )=\left (\prod _{t=u+1}^{x-1} \left (\frac{t+1}{t+4}\right )\right )=\frac{(u+2)(u+3)(u+4)}{(x+1)(x+2)(x+3)},\left (\prod _{t=u+1}^{x-1} \left (1-\frac{3}{t+4}\right )\right )=\left (\prod _{t=u+1}^{x-1} \left (\frac{t+1}{t+4}\right )\right )=\frac{(u+2)(u+3)(u+4)}{(x+1)(x+2)(x+3)},$$
replacing we get
$$f(x)=12\sum _{u=0}^{x-1}\frac{\binom{u+5}{4}4!H_{u+5}}{(x+1)(x+2)(x+3)}=\frac{12\cdot 4!}{(x+1)(x+2)(x+3)}\left (\sum _{u=0}^{x+4}\binom{u}{4}H_{u}-\sum _{u=0}^4\binom{u}{4}H_{u}\right )f(x)=12\sum _{u=0}^{x-1}\frac{\binom{u+5}{4}4!H_{u+5}}{(x+1)(x+2)(x+3)}=\frac{12\cdot 4!}{(x+1)(x+2)(x+3)}\left (\sum _{u=0}^{x+4}\binom{u}{4}H_{u}-\sum _{u=0}^4\binom{u}{4}H_{u}\right )$$
using your professors hint(which is a good exercise of integration by parts), we get that
$$f(x)=\frac{12\cdot 4!}{(x+1)(x+2)(x+3)}\left (\binom{x+5}{5}H_{x+5}-\frac{1}{5}\binom{x+5}{5}-\frac{25}{12}\right )f(x)=\frac{12\cdot 4!}{(x+1)(x+2)(x+3)}\left (\binom{x+5}{5}H_{x+5}-\frac{1}{5}\binom{x+5}{5}-\frac{25}{12}\right )$$
Taking back the change of variable, meaning plugging at $$x-4,x-4,$$ we get
$$na_n=f(n-4)=\frac{12\cdot 4!}{(n-3)(n-2)(n-1)}\left (\binom{n+1}{5}H_{n+1}-\frac{1}{5}\binom{n+1}{5}-\frac{25}{12}\right )na_n=f(n-4)=\frac{12\cdot 4!}{(n-3)(n-2)(n-1)}\left (\binom{n+1}{5}H_{n+1}-\frac{1}{5}\binom{n+1}{5}-\frac{25}{12}\right )$$