# 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?

-
You could try $b_n=na_n$. Then your recurrence becomes $\frac{b_n}{n}=b_{n-1}+b_{n-2}$ –  vadim123 Apr 25 '13 at 13:58
That's the recurrence relation for the dearrangements problem (hatcheck problem), which is solved using calculus. I guess there is no way to circumvent that little devil, calculus that is.. –  Vigneshwaren Apr 25 '13 at 16:17
@Vigneshwaren, it is close to the derangements recurrence $D_n = (n - 1) (D_{n - 1} + D_{n - 2})$, but not the same. –  vonbrand Apr 25 '13 at 18:03

## 3 Answers

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...)

-
That was brilliant and helpful, and this is gonna take some of my time. Thanks –  Vigneshwaren Apr 26 '13 at 16:40

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}$

-

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.

-
You should really add this as an edit to your question. –  vonbrand Apr 26 '13 at 18:54