Stirling Number of second kind (unsigned) and binomial coefficient, proof of equality? I have to prove the following equality concerning Stirling numbers of second kind and the binomial coefficient. And it does not matter which technique I use for my proof. But I personally wanted to prove this by induction. The problem is that I just do not know how to start the induction??? If anybody would give me a little hint how I can start the base case that would be really great ! (greetings from germany) 
prove for $n,k \in \mathbb{N}_0$
\begin{equation*}
\begin{Bmatrix}
n\\  k
\end{Bmatrix}
=\frac{1}{k!}\sum\limits_{i \in [0,k]}(-1)^{k-i}\binom{k}{i}i^n
\end{equation*}
 A: This  can  be  derived   quite  easily  using  exponential  generating
functions but  I would go for inclusion-exclusion  if a self-contained
proof is asked. Re-write your formula like so
$${n\brace k} \times k!
= \sum_{j=0}^k {k\choose j} (-1)^j (k-j)^n.$$
The left side  counts ordered set partitions into $k$  sets, so we may
imagine  these as  a row  of $k$  boxes with  $n$ labeled  balls being
distributed into them. We now  do inclusion-exclusion where a node $P$
of the  underlying poset represents  distributions where the  boxes in
$P$ were  empty, plus some  additional empty boxes possibly.   Now for
$|P|=j$ we get ${k\choose j}$  choices for the boxes and we distribute
the balls  into the remaining $k-j$  boxes for a  factor of $(k-j)^n.$
This ensures that the chosen $j$ boxes or more are empty. Observe that
we  could  in   fact  lower  the  upper  limit   to  $k-1$  because  a
configuration with  $j=k$ empty  boxes is not  possible when  $n\ge 1$
(zero contribution due to $k-j=0$).  Now in this poset the desired set
partitions into non-empty  sets appear just once when  $j=0$ and hence
have weight one. The weight of a set partition  with exactly $p$ empty
boxes  where $0\lt  p\lt k$  is (included  in all  nodes $P$  that are
subsets of the $p$ empty boxes)
$$\sum_{j=0}^p {p\choose j} (-1)^j = 0$$
because $p\ge  1.$ These partitions  have total weight zero,  only the
partitions with no  empty boxes contribute and do so  with a weight of
one and we conclude the proof.
Remark. One way to solve this by induction is to introduce the OGF
$$G_n(z) = \sum_{k\ge 0} z^k
\frac{1}{k!} \sum_{j=0}^k {k\choose j} (-1)^{k-j} j^n$$
which counts set partitions of $n$ into some number of $k$ sets.
This OGF in fact has a finite number of terms. We obtain
$$G_n(z) = \sum_{j\ge 0} j^n
\sum_{k\ge j} \frac{1}{k!} {k\choose j} (-1)^{k-j} z^k
\\ = \sum_{j\ge 0} \frac{j^n}{j!}
\sum_{k\ge j} \frac{1}{(k-j)!} (-1)^{k-j} z^k
\\ = \sum_{j\ge 0} \frac{j^n}{j!} z^j
\sum_{k\ge 0} \frac{1}{k!} (-1)^{k} z^k
\\ = \exp(-z) \sum_{j\ge 0} \frac{j^n}{j!} z^j.$$
We now claim that $G_n(z) = H_n(z)$ where
$$H_n(z) = \sum_{k\ge 0} {n\brace k} z^k.$$
We prove this by induction on $n.$ We get for $n=1$ as the base case
$$\exp(-z) \sum_{j\ge 1} \frac{j}{j!} z^j
= z \exp(-z) \exp(z) = z.$$
This holds,  for $n=1$ there is  just one possible value  of $k$ which
yields a  partition into  non-empty subsets, which  is one.   In other
words
$$G_1(z) = z = \sum_{k\ge 0} {1\brace k} z^k = H_1(z).$$
Now we have by basic combinatorics the recurrence
$${n+1\brace k} = k {n\brace k} + {n\brace k-1}.$$
This represents where  we put the value $n+1,$ in  one of the existing
$k$ subsets  or in a new  singleton subset. Multiply  by $z^{k-1}$ and
sum over $k\ge 1$ to get
$$\sum_{k\ge 1} {n+1\brace k} z^{k-1}
= \sum_{k\ge 1} k {n\brace k} z^{k-1}
+ \sum_{k\ge 1} {n\brace k-1} z^{k-1}.$$
This is
$$\frac{1}{z} H_{n+1}(z) = H_n'(z) + H_n(z)$$
or alternatively
$$H_{n+1}(z) = z H_n'(z) + z H_n(z).$$
Using the induction hypothesis we have $H_n(z) = G_n(z)$
and we obtain on the right
$$-z\exp(-z) \sum_{j\ge 0} \frac{j^n}{j!} z^j
+ \exp(-z) \sum_{j\ge 1} \frac{j^{n+1}}{j!} z^j
+ \exp(-z) \sum_{j\ge 0} \frac{j^n}{j!} z^{j+1}$$
The first and the last term cancel and we are left with just
$$\exp(-z) \sum_{j\ge 1} \frac{j^{n+1}}{j!} z^j $$ 
which is $G_{n+1}(z)$ and we have shown that $G_{n+1}(z) = H_{n+1}(z)$
which concludes the argument (on extracting coefficients we obtain the
conjectured sum formula for ${n+1\brace  k}$). Note that some of these
manipulations are not necessarily the  most effective, the goal was to
comply with the request for a proof  by induction. All of this is done
using formal power series but in  fact the series that appear converge
everywhere  and represent  entire  functions, since  the $G_n(z)$  are
polynomials.
