Proof of equation $\sum_{k}{n\brack k}a_k = n!2^{n-1}$ by induction

Question

I'm trying to prove to following equation: $$\sum_{k=0}^{n}{n\brack k} a_k = n!2^{n-1};\ \ \ n\ge 1$$ $a_n$ - number of ordered partition of set.

We have following recursion dependencies:

$a_n = \sum_{k=0}^{n-1}{n\choose k}a_k;\ \ \ \ a_0 = 1 $ And: ${n\brack k} = (n-1){n-1\brack k} + {n-1\brack k-1} $

Base of induction: $ n = 0; \ \ \ \ \ \ \ \ \ \ {0\brack 0}a_0 = 1 = 1! \cdot 2^0 = 1 $

assumption of induction: $$\sum_{k=0}^{n}{n\brack k}a_k = n!2^{n-1}$$

My attempt of proof:

$$\sum_{k=0}^{n+1}{n+1\brack k}a_k = \sum_{k=0}^{n}{n\brack k}a_k + {n+1\brack n+1}a_{n+1} = \sum_{k=0}^{n}(n{n\brack k}a_k + {n\brack k-1}a_k) + \sum_{k=0}^n {n+1\choose k}a_k = n\sum_{k=0}^n{n\brack k}a_k + \sum_{k=0}^n{n\brack k-1}a_k + \sum_{k=0}^{n}{n+1\choose k}a_k = nn!2^{n-1} + \sum_{k=0}^n ({n\brack k-1} + {n+1\choose k} )a_k $$

But I don't know how to finish it. Could you help me, please ?

Answer 1

Here is a slightly different take on this where we use generating functions and the method of annihilated coefficient extractors to verify the claim.

Recall that the species for ordered labelled set partitions is $$\mathfrak{S}(\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which gives the exponential generating function $$\sum_{n\ge 0} a_n \frac{z^n}{n!} = \frac{1}{1-z} \circ (\exp(z)-1) = \frac{1}{2-\exp(z)} = \frac{1}{2}\frac{1}{1-\exp(z)/2}.$$

Introduce $Q(z)$ the exponential generating function for the sum so that $$Q(z) = \sum_{n\ge 0} \frac{z^n}{n!} \sum_{q=0}^n \left[n\atop q\right] a_q.$$

Recall the species of permutations marked by cycle count which is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z}))$$ so that it has the generating function $$\exp\left(u \log\frac{1}{1-z}\right)$$ and we have $$\left[n\atop q\right] = n! [z^n] [u^q] \exp\left(u \log\frac{1}{1-z}\right).$$

Substitute this into $Q(z)$ to obtain $$Q(z) = \sum_{n\ge 0} \frac{z^n}{n!} \sum_{q=0}^n a_q \times n! [z^n] \frac{1}{q!} \left(\log\frac{1}{1-z}\right)^q \\ = \sum_{q\ge 0} \frac{a_q}{q!} \sum_{n\ge q} z^n [z^n] \left(\log\frac{1}{1-z}\right)^q.$$

The inner sum is the promised annihilated coefficient extractor and hence simplifies to $$Q(z) = \sum_{q\ge 0} \frac{a_q}{q!} \left(\log\frac{1}{1-z}\right)^q$$

Compare this with the generating function of the $a_q$ to obtain $$Q(z) = \frac{1}{2-\exp\left(\log\frac{1}{1-z}\right)} = \frac{1}{2 - 1/(1-z)} = \frac{1-z}{2(1-z)-1} = \frac{1-z}{1-2z}.$$

The conclusion is that $$n! [z^n] Q(z) = n! (2^n-2^{n-1}) = n! \times 2^{n-1}.$$

There is another annihilated coefficient extractor at this MSE link.

Addendum. Here is a slightly different version of the proof.

Recall once more the species of permutations marked by cycle count which is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{\ge 1}(\mathcal{Z}))$$

so that it has the generating function $$\exp\left(u \log\frac{1}{1-z}\right)$$

and in particular $$\sum_{n\ge q} \left[n\atop q\right] \frac{w^n}{n!} = \frac{1}{q!} \left(\log\frac{1}{1-w}\right)^q.$$

Continuing, recall the species of set partitions marked by the number of sets which is $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$

so that it has the generating function $$\exp\left(u (\exp(z)-1)\right)$$ and in particular $$\sum_{n\ge q} {n\brace q} \frac{w^n}{n!} = \frac{1}{q!} \left(\exp(w)-1\right)^q.$$

We have by inspection that $$a_q = \sum_{p=1}^q p! \times {q\brace p}.$$

Introduce the exponential generating function $P(z)$ of the sum we want to compute so that $$P(z) = \sum_{n\ge 1} \frac{z^n}{n!} \sum_{q=1}^n \left[n\atop q\right] a_q = \sum_{n\ge 1} \frac{z^n}{n!} \sum_{q=1}^n \left[n\atop q\right] \sum_{p=1}^q p! \times {q\brace p}.$$

Reverse the order of summation to get $$\sum_{p\ge 1} p! \sum_{q\ge p} {q\brace p} \sum_{n\ge q} \left[n\atop q\right] \frac{z^n}{n!}.$$

We recognize the closed form of the inner sum (partitions into $q$ cycles) and substitute it into this last term to get

$$\sum_{p\ge 1} p! \sum_{q\ge p} {q\brace p} \frac{1}{q!} \left(\log\frac{1}{1-z}\right)^q$$

The new inner sum also has a simple closed form (partitions into $p$ sets) composed with the logarithmic term. Applying this we obtain $$\sum_{p\ge 1} p! \times \frac{1}{p!} \left(\exp\log\frac{1}{1-z} - 1\right)^p = \sum_{p\ge 1} \left(\frac{1}{1-z} - 1\right)^p \\ = \sum_{p\ge 1} \left(\frac{z}{1-z}\right)^p = \frac{z/(1-z)}{1-z/(1-z)} = \frac{z}{1-2z}.$$

We once more obtain $$n! [z^n] P(z) = n! [z^n] \frac{z}{1-2z} = n! [z^{n-1}] \frac{1}{1-2z} = n! \times 2^{n-1}.$$

The discrepancy between $Q(z)$ and $P(z)$ is due to the fact that the latter does not include a term for $n=0.$ There is no doubt that these two proofs are trivial variations on one another, but the second one is explicit about the dependence on the Stirling numbers of the second kind.

Answer 2

Here is a short algebraic proof that does not make use of any species theory.

Let $a(n)$ denote the $n^{\text{th}}$ ordered Bell number, which is defined as the number of ordered partitions of a set of $n$ elements.

Let $n\brack{k}$ and $S(n, k)$ denote the Stirling numbers of the first and second kind respectively.

By definition, $a(n) = \displaystyle \sum_{k=0}^{n}k!S(n,k).$ We will make use of the following infinite series for $a(n)$ to prove the required identity:

Lemma: $a(n) = \displaystyle \sum_{m=0}^{\infty}\dfrac{m^{n}}{2^{m+1}}$

Proof of lemma:

\begin{align*}\displaystyle \sum_{m=0}^{\infty}\dfrac{m^{n}}{2^{m+1}}&= \displaystyle \sum_{m=0}^{\infty}\dfrac{1}{2^{m+1}}\sum_{k=0}^{n}S(n,k)(m)_{k} \\&= \sum_{k=0}^{n}S(n,k)k!\sum_{m=0}^{\infty}\dfrac{\binom{m}{k}}{2^{m+1}}\\&= \sum_{k=0}^{n}S(n,k)k!2^{-(k+1)}\sum_{j=0}^{\infty}\binom{k+j}{j}2^{-j}\\&=\sum_{k=0}^{n}S(n,k)k!\\&=a(n)\end{align*}

In the first equality, we used the identity $x^{n} = \displaystyle \sum_{k=0}^{n}S(n, k)(x)_{k},$ a proof of which may be foundby double counting the number of functions from an $n$-set to an $x$-set. In the second equality, we used the fact that $(m)_{k} = \binom{m}{k}k!.$ In the thrid equality, note that for $m <k, \binom{m}{k}=0$ and take the $2^{-(k+1)}$ factor out and reindex the sum. In the fourth equality, we use the fact that the generating function for multiset selection is $\displaystyle\sum_{j=0}^{\infty}\binom{n+j-1}{j}x^{j} = \dfrac{1}{(1-x)^{n}}.$

Using this lemma we can prove the required identity as follows:

Proof of $\displaystyle \sum_{k=0}^{n} {n \displaystyle \brack k} a(k) = n!2^{n-1}:$

\begin{align}\displaystyle \sum_{k=0}^{n} {n \displaystyle \brack k} a(k)&= \dfrac{1}{2}\sum_{k=0}^{n} {n \displaystyle \brack k}\sum_{m=0}^{\infty}\dfrac{m^{k}}{2^{m}}\\&= \dfrac{1}{2}\sum_{m=0}^{\infty}\dfrac{1}{2^{m}}\sum_{k=0}^{n}{n \brack k}m^{k}\\&= \dfrac{1}{2}\sum_{m=0}^{\infty}\dfrac{1}{2^{m}}m(m+1)\ldots (m+n-1)\\&= \dfrac{n!}{2}\sum_{m=1}^{\infty}\dfrac{\binom{m+n-1}{n}}{2^{m}}\\&= \dfrac{n!}{4}\sum_{j=0}^{\infty}\dfrac{\binom{n+j}{j}}{2^{j}} \\&= n!2^{n-1} \end{align}

In the first equality, we used the above lemma. In the second equality, we switched the order of summation (permissible when one sum is infinite and other is finite.) In the third equality, we used the identity $x(x+1)\ldots (x+n-1) = \displaystyle\sum_{k=0}^{n}{n \brack k}x^{k},$ a proof of which may be found here. In the fourth equality, we rewrote the sum and began indexing from $1$ since the term at $0$ was $0.$ In the fifth equality, we re-indexed and in the sixth equality, we once again used the generating function identity mentioned above.