Finding a closed form for a generating function

Question

I'm working on finding explicit forms of recurrence relations for a polynomial representative of matchings of a graph, and am getting stuck when trying to go from recurrence to generating function. The recurrence is $\alpha(K_n) = \lambda\alpha(K_{n-1})-(n-1)\alpha(K_{n-2})$, where $n\geq 2$ and $\alpha(K_0) =1,\alpha(K_1) = \lambda$. I'm attempting to use an ordinary generating function, defined as $f(x) = \displaystyle\sum_{i=0}^{\infty}\alpha(K_i)x^i$: \begin{align} f(x) &= 1+\lambda x + \sum_{i=2}^{\infty}\alpha(K_i)x^i\\ &= 1+\lambda x+\sum_{i=2}^{\infty}(\lambda\alpha(K_{i-1})-(i-1)\alpha(K_{i-2}))x^i\\ &= 1+\lambda x+\lambda x\left(\sum_{i=0}^{\infty}\alpha(K_i)x^i -1 \right)-\sum_{i=2}^{\infty}(i-1)\alpha(K_{i-2})x^i, \end{align} but I get stuck trying to relate the last term back to $f(x)$. Are there tricks for dealing with coefficients dependent on the index in this kind of generating function? There are some sources that suggest an exponential generating function may be better, but I don't know where to start with that, since in this scenario there aren't any factorials to deal with. Is there something I'm missing?

Answer 1

1. write $u_n=\alpha(K_n)$ 2) if $f(x)=\sum_{n=1}^{\infty}u_nx^n$ find the polynomials $A,B,C$ such that $Af'+Bf+C=0.$ 3) integrate this differential equation.

Start the clock: less than one hour if you are extremely careful.