Homogenous Recurrence with Quadratic Coefficients

Question

I wonder if there is a general method for studying second-order homogeneous recurrence relations with quadratic coefficients. I'm considering the following:

$$S_k = a S_{k-1} - (b-k) (k-1) S_{k-2}$$

with $S_0 = 1$ and $S_1 =a$.

Answer 1

Generating functions are a pretty good bet. Define $F(x) = \sum_{k=0}^\infty S_k x^k$. Now take your equation above and multiply both sides by $x^k$ getting

$$S_k x^k = a S_{k-1}x^k - (k^2 - (b+1)k + b) S_{k-2}x^k.$$

Next sum from $k=2$ to infinity to get

$$\sum_{k=2}^\infty \left( S_k x^k \right) = \sum_{k=2}^\infty \left( a S_{k-1}x^k\right) - \sum_{k=2}^\infty \left( (k^2 - (b+1)k + b) S_{k-2}x^k\right).$$

The LHS is just $F(x) -ax-1$, and we can start messing around with the right hand side to get it in terms of $F(x)$ and it's derivatives. Eventually we'll get a second order differential equation. Solving that differential equation and examining the Maclaurin series of the solutions gets us a simplified expression for $S_k$.