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*}
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.