# Exponential Generating Function for the recurrence relation $a_n=\sum_{k=1}^n {n\choose k}a_{n-k}$

Here is the problem (this is problem 66 part iii) from page 280 of Principles and Techniques in Combinatorics):

Given the recurrence relation $$a_n=\sum_{k=1}^n {n\choose k}a_{n-k}$$, with $$a_0=1$$, show that the exponential generating function for $$a_n$$, $$A(x)=\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}$$ is equal to $$\frac{1}{2-e^x}$$.

I have pretty much worked out a solution, but my final answer is missing a $$1$$. Here is my solution.

Plug in $$a_n$$ into $$A(x)$$: $$$$A(x)=\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}=\sum_{n=0}^{\infty}(\sum_{k=1}^n {n\choose k}a_{n-k})\frac{x^n}{n!} \\ Note: a_n=\sum_{k=1}^n {n\choose k}a_{n-k}=(\sum_{k=0}^n {n\choose k}a_{n-k})-a_n \\\implies A(x)=\sum_{n=0}^{\infty}((\sum_{k=0}^n {n\choose k}a_{n-k})-a_n\frac{x^n}{n!}) \\=\sum_{n=0}^{\infty}(\sum_{k=0}^n \frac{n!}{k!(n-k)!}a_{n-k})\frac{x^n}{n!}-\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}=\sum_{n=0}^{\infty}((\sum_{k=0}^n \frac{a_{n-k}}{k!(n-k)!})x^n)-A(x) \\=(\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n)(\sum_{n=0}^{\infty}\frac{x^n}{n!})-A(x)=A(x)e^x-A(x) \\\implies A(x)=A(x)e^x-A(x)$$$$ Which, obviously does not give the desired result of $$A(x)=\frac{1}{2-e^x}$$. I'm assuming I'm messing up some index or something, but I've picked over the computation over and over and haven't found any mistakes. Can anyone point my mistake out?

• Here is a method to find the mistake. Work our the first few terms, $a_0,\dots, a_4$. Then plug in that starting part of $A(x)$ in one of the formulas near the middle. Find out whether your mistake is before that point or after. Repeat. Dec 6 '20 at 18:30
• You substitute $a_n=(\sum_{k=0}^n {n\choose k}a_{n-k})-a_n$ for all $n$, but I don't think it works for $n=0$ (gives $1=1-1=0$ if I am not missing something). I suggest to move terms corresponding to the $n=0$ out of the sum and handle separately.
– Sil
Dec 6 '20 at 18:32
• @Sil Thanks, I see that that indeed that doesn't work. Dec 6 '20 at 18:43

As pointed out in comments, at $$n=0$$ the "note" fails; you need to separate out this case beforehand. $$A(x)=\sum_{n=0}^\infty a_n\frac{x^n}{n!}=1+\sum_{n=1}^\infty a_n\frac{x^n}{n!}=1+\sum_{n=1}^\infty\sum_{k=1}^n \binom nka_{n-k}\frac{x^n}{n!}$$ $$=1+\sum_{n=1}^\infty\sum_{k=0}^n \binom nka_{n-k}\frac{x^n}{n!} - \sum_{n=1}^\infty a_n\frac{x^n}{n!}=2+\sum_{n=1}^\infty\sum_{k=0}^n \binom nka_{n-k}\frac{x^n}{n!} - A(x)$$ $$=1+\sum_{n=0}^\infty\sum_{k=0}^n \binom nka_{n-k}\frac{x^n}{n!} - A(x)=\cdots=1+A(x)e^x-A(x)$$
\begin{align} A(x) &= \sum_{n \ge 0} a_n \frac{x^n}{n!} \\ &= a_0 + \sum_{n \ge 1} a_n \frac{x^n}{n!} \\ &= 1 + \sum_{n \ge 1} \sum_{k=1}^n \binom{n}{k} a_{n-k} \frac{x^n}{n!} \\ &= 1 + \sum_{k \ge 1} \sum_{n\ge k} \frac{n!}{k!(n-k)!} a_{n-k} \frac{x^n}{n!} \\ &= 1 + \sum_{k \ge 1} \frac{x^k}{k!} \sum_{n\ge k} a_{n-k} \frac{x^{n-k}}{(n-k)!} \\ &= 1 + \sum_{k \ge 1} \frac{x^k}{k!} A(x) \\ &= 1 + (e^x-1) A(x), \end{align} so $$A(x) = \frac{1}{2-e^x}$$