$b_n=\frac{(-n)^{n-1}}{n!}$ recursive form proof

Question

How can I prove that this recursive sequence:$$a_{n}=\begin{cases}n & n=1\\\frac{n}{2-2n}\sum_{k=1}^{n-1}a_{k}a_{n-k} & \text{else}\end{cases}$$And this series:$$b_n=\frac{(-n)^{n-1}}{n!}$$Are equal?

Answer 1

First, start as Arthur and Michael Jesurum said in their comment. We'll show $$\frac{(-n)^{n-1}}{n!}=\frac{n}{2-2n}\sum_{k=1}^{n-1}\frac{(-k)^{k-1}(-(n-k))^{n-k-1}}{k! (n-k)!}$$ Multiplying $n!$ in both sides and clearing minus signs give a equivalent form, $$n^{n-1} = \frac{n}{2n-2} \sum_{k=1}^{n-1} \pmatrix{n \\ k} k^{k-1} (n-k)^{n-k-1}$$ Simplifying a bit gives $$2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \pmatrix{n \\ k} k^{k-2} (n-k)^{n-k-2} k(n-k)$$ The reason why I made lots of $m^{m-2}$ is to use Caley's theorem, which states that the number of distinct trees made by (distinct) $m$ vertices is $m^{m-2}$. (It also holds if $m=1$)

Let's make tree with vertices named $1, 2, \cdots, n$, and count how many trees are there. For each $k=1, 2, \cdots, n-1$, we will do the following:

Choose $k$ vertices from $1, 2, \cdots, n$. (There are $\pmatrix{n\\k}$ ways to do this.) Let's call them $A$, and other $n-k$ vertices $B$. Make any tree with $k$ vertices in $A$. (There are $k^{k-2}$ ways to do this.) Make any tree with $n-k$ vertices in $B$. (There are $(n-k)^{n-k-2}$ ways to do this.) From each tree, choose one point. (There are $k(n-k)$ ways to do this.) Finally, connect two chosen points. Then, we get a tree with vertices $1, 2, \cdots, n$.

Obviously, by our rule, the number of trees are $$\sum_{k=1}^{n-1} \pmatrix{n\\k} k^{k-2} (n-k)^{n-k-2} k(n-k) $$ Now count trees in another way, namely, for each possible tree (with $n$ vertices), count how many trees of same type are there. Choose any tree $T$ with $n$ vertices. (There are $n^{n-2}$ ways to do this.) $T$ is made when one of the $T$'s edge is connected in the last step of above rule. (There are $n-1$ candidate of such edge.) Also, $A$ and $B$ can interchange their rule without affecting $T$. (This gives a coefficient $2$.)

By above reasoning, the number of trees are $$ 2(n-1)n^{n-2}$$

There were no woodcutter and nobody planted tree while we were counting trees. So we have $$\sum_{k=1}^{n-1} \pmatrix{n\\k} k^{k-2} (n-k)^{n-k-2} k(n-k) = 2(n-1)n^{n-2}$$