1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – GEdgar
    Dec 6 '20 at 18:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sil
    Dec 6 '20 at 18:32
  • $\begingroup$ @Sil Thanks, I see that that indeed that doesn't work. $\endgroup$ Dec 6 '20 at 18:43
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.