# Proving a recurrence relationship for a sequence

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?

• Aside: I think the question, in place of "Let $B(x)$ be the recurrence relation for the sequence $b_n$", should have "Let $B(x)$ be the [exponential] generating function for the sequence $b_n$". – ShreevatsaR May 5 '14 at 4:17
• @ShreevatsaR Yeah, I think so, too. That's what was throwing me off to begin with. Then I assumed that I just needed to find an EGF for $b_n$, which is how I got on to the track mentioned above. – BSnapZ May 5 '14 at 4:21
• Yes definitely the right question is to find an EGF; note that $\exp(x + x^2/2) = 1+x+\frac{2x^2}{2!}+ \frac{4x^3}{3!} + \frac{10x^4}{4!} + \dots$ and the coefficients satisfy the recurrence. – ShreevatsaR May 5 '14 at 8:34
• I can see that it is satisfied, but only because I know that it should be. How do I got about proving this, though? – BSnapZ May 5 '14 at 8:46
• I think I've come up with a good solution and have just posted it as an answer. – BSnapZ May 6 '14 at 10:27

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!

• Really nice solution, congratulations. :-) The main trick seems to be making sure that the $(n-1)b_{n-2}$ term gets multiplied by $x^{n-1}/(n-1)!$ rather than say $x^n/n!$ or $x^{n-2}/(n-2)!$, so that the $(n-1)$ factor cancels cleanly and we don't have to solve too-complicated differential equations. – ShreevatsaR May 6 '14 at 16:24
• @ShreevatsaR Thanks! You're right, that does seem to be the trick. – BSnapZ May 6 '14 at 19:13