Solve the recurrence relation: $na_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. $$
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.
 A: 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 )$$
A: Here are more details for @Phicar's suggested approach.
Let $A(z)=\sum_{n \ge 0} a_n z^n$ be the ordinary generating function of $(a_n)$.
Then $z A'(z)=\sum_{n \ge 0} n a_n z^n$, and the recurrence relation implies that
\begin{align}
z A'(z) 
&= \sum_{n \ge 5} \left((n-4)a_{n-1} + 12n H_n\right) z^n \\
&= z \sum_{n \ge 5} (n-1) a_{n-1} z^{n-1} - 3 z \sum_{n \ge 5} a_{n-1} z^{n-1} + 12z \sum_{n \ge 5} n H_n z^{n-1} \\
&= z \cdot z A'(z) - 3z A(z) + 12z\left(\frac{d}{dz}\left(\frac{-\log(1-z)}{1-z}\right) -\sum_{n=1}^4 n H_n z^{n-1}\right) \\
&= z^2 A'(z) - 3z A(z) + 12z\left(\frac{1-\log(1-z)}{(1-z)^2} -1-3z-\frac{11}{2}z^2-\frac{25}{3}z^4\right)
\end{align}
The resulting solution for $A(z)$ is messy, so there must be a better way.
A: Given by a CAS.
Isuppose that is missing the condition $a_3=0$.
Starting from $n=5$, the sequence
$$\left\{\frac{137}{25},\frac{1009}{150},\frac{17953}{2450},\frac{151717}{19600},\frac{
   170875}{21168},\frac{1474379}{176400},\frac{3751927}{435600},\frac{20228477}{22869
   00}\right\}$$ is not recognized by $OEIS$.
Being totally stuck, I used a CAS without conditions and got, after a lot of simplifications,
$$a_n=\frac{(-3 n^4+22 n^3-69 n^2+194 n+288+96 C) } {4 (n-3) (n-2) (n-1) n }+$$ $$\frac{12 (n-4) (n+1) \left(n^2-3 n+6\right) H_{n+1} } {4 (n-3) (n-2) (n-1) n }$$
For $n=0,1,2,3$, this leads to indeterminate forms. For $n=4$
$$a_4=C+\frac{25}{4}=0 \implies C=-\frac{25}{4}$$ leading to
$$a_n=(n-4)\frac{12 (n+1) \left(n^2-3 n+6\right) H_{n+1}-(n-3) \left(3 n^2-n+26\right) } {4 (n-3) (n-2) (n-1) n }$$ which is identical to what @Raffaele wrote in a comment.
Asymptotically,
$$a_n=3 \left(\gamma -\frac{1}{4}\right)+3 \log (n)+\frac{11}{2 n}-\frac{25}{4
   n^2}+O\left(\frac{1}{n^3}\right)$$
I would really like to know how, starting from scratch, we could arrive to the result.
A: I have one different idea, variation of constant.
If one has a recurrence relation of the form
$$ a_{n+1} = \alpha_n a_n + \beta_n,\quad n\geq 0, $$
then we can make the ansatz
$$ a_n^{(p)} = C_n \prod_{j=}^{n-1} \alpha_j $$
and get
$$ C_{n+1} \prod_{j=0}^n \alpha_j = \alpha_n C_n \prod_{j=0}^{n-1} \alpha_j + \beta_n $$
$$ \Longrightarrow C_{n+1} = C_n + \frac{\beta_n}{\prod_{j=0}^n \alpha_j} $$
$$ \Longrightarrow C_n = \sum_{l=0}^{n-1} \frac{\beta_l}{\prod_{j=0}^l \alpha_j} + C_0$$
and therefore
$$ a_n = \sum_{l=0}^{n-1} \frac{\beta_l}{\prod_{j=0}^l \alpha_j} \prod_{j=0}^{n-1} \alpha_j + C \prod_{j=0}^{n-1} \alpha_j = \sum_{l=0}^{n-1} \frac{12 H_{l+1}}{\prod_{j=0}^l \frac{j-3}{j+1}} \prod_{j=0}^{n-1} \frac{j-3}{j+1} + C \prod_{j=0}^{n-1} \frac{j-3}{j+1} \\= \sum_{l=0}^{n-1} 12 H_{l+1} \prod_{j=l+1}^{n-1} \frac{j-3}{j+1} + C \prod_{j=0}^{n-1} \frac{j-3}{j+1},$$
if we define
$$ \alpha_n = \frac{n-3}{n+1},\qquad \beta_n = 12 H_{n+1}.$$
I do not know how to continue from here, maybe someone knows how to simplify this terms to get to the solution?
A: Let $f\left( x \right) = \sum\limits_{n = 0}^\infty  {a_n x^n } $ be the generating function of the solution of the recurrence.
$$
\sum\limits_{n = 0}^\infty  {na_n x^n }  = \sum\limits_{n = 0}^\infty  {\left( {n + 1} \right)a_n x^{n + 1}  - 4\sum\limits_{n = 0}^\infty  {a_{n - 1} x^n } }  + 
12\sum\limits_{n = 5}^\infty  {na_n x^n } H_n 
$$
which gives the following DE
$$
xf'\left( x \right) = x^2 f'\left( x \right) - 3xf\left( x \right)-\frac{2 x \left(50 x^5-67 x^4+2 x^3+3 x^2+6 x+6 \log (1-x)\right)}{(x-1)^2}$$
Whose solution is
$$f(x)=\frac{2}{75 (x-1)^2} \left(-7553 x^5+3750 x^5 \log (1-x)+\\+24040 x^4-18750 x^4 \log (1-x)-29405 x^3+37500 x^3 \log (1-x)+\\+16830 x^2-37500 x^2 \log (1-x)-3840 x+18750 x \log (1-x)-3840 \log (1-x)\right)$$
Coefficients of the MacLaurin expansion of $f(x)$ are
$$0,0,0,0,0,\frac{137}{5},\frac{578}{15},\frac{1667}{35},\frac{395}{7},\frac{41137}{630},\frac{13007}{175},\frac{964849}{11550},\ldots$$
There is no closed form for $a_n$, though.
