Solving recurrence equation using exponential generating functions

Question

The recurrence is

$ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $

I tried using exponential generating functions and have problems with it (the second term mostly) Further can this be solved without reducing it to a differential equations?

Answer 1

Define $A(z) = \sum_{n \ge 0} a_n \frac{z^n}{n!}$. Write: $$ a_{n + 2} = (n + 1) a_{n + 1} + n a_n $$ From properties of exponential generating functions: $$ \begin{align*} A''(z) &= (z \frac{d}{d z} + 1) A'(z) + z A'(z) \\ A''(z) &= z A''(z) + (1 + z) A'(z) \end{align*} $$ This looks second order, but is a homogeneous linear first order differential equation for $A'(z)$. Courtesy of maxima we have for some $c_1$: $$ A'(z) = \frac{c_1 e^{-z}}{(1 - z)^2} $$ This gets ugly... maxima integrates this to: $$ A(z) = c_2 + \frac{c_1 E_2(z - 1)}{1 - z} $$ where: $$ E_2(z) = z \int_z^\infty \frac{e^{-t} d t}{t} $$ NIST has details on this function.

Expanding $A'(z)$ in series (multiply the exponential by the series for $(1 - z)^{-2}$) and integrating term by term might be a nicer bet...

$$ \begin{align*} A'(z) &= c_1 \sum_{k \ge 0} \binom{-2}{k} (-z)^k e^{-z} \\ &= c_1 \sum_{k \ge 0} \binom{k + 1}{1} z^k e^{-z} \\ &= c_1 \sum_{k \ge 0} (k + 1) z^k e^{-z} \\ A(z) &= c_2 - c_1 \sum_{k \ge 0} (n + 1) \int_z^\infty t^k e^{-t} d t \end{align*} $$ Too bad that the integrals don't give any sort of nice polynomials... would need to set up a recurrence for those by integration by parts.

Edit

Do I feel dumb... when I do know that if: $$ C(z) = \sum_{n \ge 0} c_n z^n $$ then: $$\frac{C(z)}{1 - z} = \sum_{n \ge 0} \left( \sum_{0 \le k \le n} c_k \right) z^n $$ For an exponential generating function it is $a_0 = A(0)$, $a_1 = A'(0)$. So we can say: $$ \begin{align*} A'(z) &= \frac{a_1 e^{-z}}{(1 - z)^2} \\ &= a_1 \sum_{n \ge 0} \left( \sum_{0 \le r \le n} \sum_{0 \le s \le r} \frac{(-1)^s}{s!} \right) z^n \end{align*} $$ This gives: $$ \frac{a_n}{n!} = [n = 0] a_0 + [a > 0] a_1 \sum_{0 \le r \le n - 1} \sum_{0 \le s \le r} \frac{(-1)^s}{s!} $$ Summing by parts: $$ \sum_{0 \le r \le n - 1} \sum_{0 \le s \le r} \frac{(-1)^s}{s!} = n \sum_{0 \le s \le n} \frac{(-1)^s}{s!} - 0 \cdot 1 - n \cdot \frac{(-1)^n}{n!} = n \sum_{0 \le s \le n - 1} \frac{(-1)^s}{s!} $$ So: $$ a_n = [n = 0] a_0 + a_1 n! \cdot n \sum_{0 \le s \le n - 1} \frac{(-1)^s}{s!} $$ (I think something isn't quite right here, but I'm tired...)

Answer 2

By vadim123's hint, the substitution $b_{n + 1} = n a_n$ gives: $$ b_{n + 1} = n (b_n + b_{n - 1}) $$ Defining the exponential generating function $B(z) = \sum_{n \ge 0} b_n \frac{z^n}{n!}$, by properties of exponential generating functions: $$ \begin{align*} B'(z) &= z B'(z) + z \frac{d}{dz} \int B(z) \\ B'(z) (1 - z) &= z B(z) \\ B(z) = \frac{c e^{-z}}{1 - z} \end{align*} $$ From here: $$ \begin{align*} b_n &= c n! \sum_{0 \le k \le n} \frac{(-1)^k}{k!} \\ a_n &= c (n + 1) (n - 1)! \sum_{0 \le k \le n - 1} \frac{(-1)^k}{k!} \end{align*} $$ Ugly as they come... but at least $a_n \approx c (n + 1) (n - 1)! e^{-1}$

Answer 3

The original problem which follows this recursion is:

A good permutation of {1,2,..., n} is one which doesn't
have two consecutive numbers (like {1,2} etc.). Find the number
of such permutations.

I figured the recursion which was fun to construct. I was later told that this was somehow related to Euler's totient function $\phi$, which I don't see how though. But most importantly the proof of this recursion is what makes it fun and interesting.