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

Question

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.

Answer 1

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 )$$

Answer 2

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.

Answer 3

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.

Answer 4

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?

Answer 5

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.