$$ t_{n}=\left\{\begin{array}{ll}{0} & {\text { if } n<1} \\ {n-1+\frac{1}{n^{2}} \sum_{k=1}^{n}\left[(k-1) t_{k-1}+(n-k) t_{n-k}\right]} & {\text { otherwise }}\end{array}\right. $$
Let $T(z)$ be a generating function for $t_n$: $$ T(z) = t_0 + t_1 z + t_2 z^2 +\ldots + t_n z^n + \ldots $$ Show that $$ T''(z) = \frac{3z-1}{z(1-z)} T'(z) + \frac{2z+4}{(1-z)^4} $$
Can anyone share thoughts on solving this question?
Notice (and remember) that
$$\frac{3z - 1}{z(1 - z)} = -\frac{1}{z} + \sum_{n = 0}^\infty2z^n$$
and
$$\frac{2z + 4}{(1 - z)^4} = \sum_{n = 0}^\infty(n + 1)(n + 2)^2 z^n$$
using geometric series and binomial series.
Now we can rewrite the one we wanted to show as $$\sum_{n = 0}^\infty (n +2)(n+1)t_{n +2} z^n = \left(-\frac{1}{z} + \sum_{n = 0}^\infty2z^n\right)\sum_{n = 0}^\infty (n + 1)t_{n + 1}z^n + \sum_{n = 0}^\infty (n + 1)(n + 2)^2 z^n.$$
We now compare the coefficient of $z^n$ on both sides.
For $n \geq 0$ the cofficient of $z^n$ in the first term on the right hand side is $$-(n + 2)t_{n +2} + \sum_{k = 0}^n 2(n - k + 1)t_{n - k + 1}$$ (To get $z^n$, we multiply $z^k$ in the $-1/z +\sum_{n = 0}^\infty$ and $z^{n - k}$ in $T'(z)$ )
Thus, the cofficient of $z^n$ on the right hand side is $$ -(n + 2)t_{n +2} + \sum_{k = 0}^n 2(n - k + 1)t_{n - k +1} + (n + 1)(n + 2)^2$$ and on the left hand side is $(n + 1)(n + 2)t_{n + 2}$.
simplifying we got $$(n + 2)^2t_{n + 2} = (n + 1)(n + 2)^2 + \sum_{k = 0}^n 2(n - k+1)t_{n - k+1}.$$
Can you continue from here?
The only thing you need to show is $$\sum_{k = 0}^n 2(n + 1 - k)t_{n + 1 - k} = \sum_{k = 1}^{n + 2} [(k - 1)t_{k - 1} + (n + 2 - k)t_{n + 2 - k}]$$
Hint: Try tho change the index of summation on the left hand side and use the fact that $2x = x + x$.