TITLE: Solve the recurrence relation: $na_n = (n-4)a_{n-1} + 12n H_n$
QUESTION [2 upvotes]: 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. $$
Does anyone have an idea, what could be substituted for $a_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} $$
to simplify the result.

REPLY [3 votes]: Here is a different approach: Consider the change of variable $b_n=a_{n+4},$ so that the only initial condition is given by $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)b_{n+1}-(n+4)b_{n}+3b_{n}-12(n+5)H_{n+5}=0,$$
take $f(x)=(x+4)b_x$ so that $$\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}.$$
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 ),$$
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)},$$
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 )$$
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 )$$
Taking back the change of variable, meaning plugging at $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 )$$
{"set_name": "stack_exchange", "score": 2, "question_id": 3889303}