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)$:
\begin{equation}
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)
\end{equation}
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?
Best Answer
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)$$