I have an assignment question which I have spent hours working on without getting even close to the answer, and would really appreciate any pointers that could help me figure it out.
QUESTION
Let $b_n$ be the number of ways a set of size $n$ can be split into singletons and pairs (i.e. a partition into subsets of size 1 or 2). Then $b_n= b_{n-1} + (n-1)b_{n-2}$ (where $n\ge1$). Let $B(x)$ be the recurrence relation for the sequence $b_n$.
Show that $B(x)=e^{x+\frac{x^2}{2}}$.
ATTEMPTS SO FAR
In order for the situation to make sense, I have set $b_0=b_1=1$.
Tried using the recursive formula to derive an Ordinary Generating Function. $B(x)=\sum_{n\ge0}b_nx^n=b_0+\sum_{n\ge1}(b_{n-1}+(n-1)b_{n-2})x^n=...nothing...happy...$
I'm sure that an Exponential Generating Function is the way to go (seeing as the equation we want to end up with is exponential). But the working seems to get complicated and I'm not sure where to go with it.
Let $B(x)=\sum_{n\ge0}\frac{b_nx^n}{n!}=b_0+\sum_{n\ge1}\frac{b_{n-1}+(n-1)b_{n-2}}{n!}x^n$
$=1+\sum_{n\ge1}\frac{b_{n-1}}{n!}x^n+\sum_{n\ge1}\frac{(n-1)b_{n-2}}{n!}x^n$
$=1+\sum_{n\ge0}\frac{b_{n}}{(n+1)!}x^{n+1}+\sum_{n\ge2}\frac{(n-1)b_{n-2}}{n!}x^n$
$=1+\sum_{n\ge0}\frac{b_{n}}{(n+1)!}x^{n+1}+\sum_{n\ge0}\frac{(n+1)b_{n}}{(n+2)!}x^{n+2}$
This is where I get stuck. I've gone over many pages of working and scribbles trying to move on from here, but I have nothing. Not a clue!
Am I on the right track at all? And if so, where should I be heading from here?
Just messing about with random tricks to see if anything helped, and I'm pretty sure I've managed to come up with a solution! I'm 99% sure that the working is legit, and I get the right generating function at the end, so I'm pretty confident. Below is my solution (if anyone has a better way, feel free to post it).
SOLUTION
Given $b_n=b_{n-1}+(n-1)b_{n-2}$, let $B(x)=\sum_{n\ge0}\frac{b_n}{n!}x^n$ be the EGF for $b_n$.
Define $b_1=b_0$ (from recurrence formula). Set $b_1=b_0=1$.
Let $m=n+1$, then $b_{m+1}=b_{m}+mb_{m-1}$
Now, the generating function for the $b_{m+1}$ must be equal to the generating function for $b_{m}+mb_{m-1}$. So we have:
$\sum_{m\ge0}\frac{b_{m+1}}{m!}x^m=\sum_{m\ge0}\frac{b_{m}}{m!}x^m+\sum_{m\ge0}\frac{mb_{m-1}}{m!}x^m$
$\sum_{m\ge1}\frac{b_m}{(m-1)!}x^{m-1}=\sum_{m\ge0}\frac{b_{m}}{m!}x^m+\sum_{m\ge1}\frac{b_{m-1}}{(m-1)!}x^m$
$\sum_{m\ge1}\frac{b_m}{(m-1)!}x^{m-1}=\sum_{m\ge0}\frac{b_{m}}{m!}x^m+x\sum_{m\ge1}\frac{b_{m-1}}{(m-1)!}x^{m-1}$
$\sum_{m\ge1}\frac{b_m}{(m-1)!}x^{m-1}=\sum_{m\ge0}\frac{b_{m}}{m!}x^m+x\sum_{m\ge0}\frac{b_m}{m!}x^m$
We know $B(x)=\sum_{n\ge0}\frac{b_n}{n!}x^n$ and we can differentiate to get $B'(x)=\sum_{n\ge1}\frac{b_n}{(n-1)!}x^{n-1}$, so substituting these values in to the above expression, we get:
$B'(x)=B(x)+xB(x)$
$B'(x)=(1+x)B(x)$
$\frac{B'(x)}{B(x)}=1+x$
Integrating both sides, we get:
$ln(B(x))=x+\frac{x^2}{2}+c$
Therefore, $B(x)=e^{x+\frac{x^2}{2}+c}$. Finally, $B(0)=b_0=1$ (as defined above).
$B(0)=e^{0+\frac{0^2}{2}+c}=e^c=1$, so $c=0$.
Hence we get the final EGF: $B(x)=e^{x+\frac{x^2}{2}}$, which is what we wanted!