Proof of equation $\sum_{k}{n\brack k}a_k = n!2^{n-1}$ by induction 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 ?
 A: 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.
A: 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.
