I've been trying to find a generating function for the Quicksort Algorithm from the recurrence $$(n+1)b_{n+1}-(n+2)b_n=2n$$
I take the generating function as $B(x)=\sum_{n\geq 0}b_nx^n$, and, as usual, try to find this sum on the recurrence once I multiply by $x^i$ and add all of them. But I've never worked with exercises like this one involving the index and I don't find a way to get $B(x)$ from expressions like $\sum_{n\geq 1}(n+1)b_{n+1}x^n$.
On
Another approach after @Donald Splutterwit's answer.
If you have $$(n+1)b_{n+1}-(n+2)b_n=2n \qquad \text{with} \qquad b_0=a$$which is not the simplest reccurence equation, you have $$b_n=\left(a+2 \psi (n+1)+2 \gamma\right)+\left(a+2 \psi (n+1)+2 \gamma -4\right)n$$ from which $$\sum_{n=0}^\infty b_n \,x^n=\frac{a-2 x-2 \log (1-x)}{(1-x)^2}$$
Let \begin{eqnarray*} B(x) = \sum_{n=1} ^{\infty} b_n x^n. \end{eqnarray*} Differentiating gives \begin{eqnarray*} B'(x) = \sum_{n=1} ^{\infty} n b_n x^{n-1}. \end{eqnarray*} Now multiply your equation by $x^{n}$ and the sum $n$ from $1$ to $ \infty$ \begin{eqnarray*} \sum_{n=1} ^{\infty} (n+1) b_{n+1} x^{n} - \sum_{n=1} ^{\infty} (n+2) b_{n} x^{n} = 2 \sum_{n=1} ^{\infty} n x^{n} \\ B'(x)-b_1 - (x B'(x)+2B(x))= \frac{2x}{(1-x)^2}\\ \end{eqnarray*} Now you just need to solve this differential equation.