Solving recurrence equation using exponential generating functions 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?
 A: 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...)
A: 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}$
A: 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.
