Explicit formula for Bernoulli numbers by using only the recurrence relation It is not hard to show, by induction on $m\in\mathbb N$, that there exist a sequence $(B_n)_{n\geq0}$ of rational numbers such that
$$\sum_{k=1}^nk^m=\frac1{m+1}\sum_{k=0}^m\binom{m+1}kB_k\,n^{m+1-k},\ \style{font-family:inherit;}{\text{for all}}\ n\geq1\,.$$
These are the Bernoulli numbers of the second kind, that is, $B_1=+1/2$. A corollary of the proof (by induction) of the fact above is a recurrence formula for such numbers $B_n$, which are known as Bernoulli numbers:
$$\sum_{k=0}^{n-1}\binom nkB_k=0\,.\tag{$\ast$}$$
On the other hand, there are a number of explicit formulae for $B_n$, which are obtained using the equality $\frac x{e^x-1}=\sum_{n=0}^\infty B_n\,\frac{x^n}{n!}$; see here and here. For example:
$$B_n=\sum_{k=0}^n\frac1{k+1}\sum_{r=0}^k(-1)^r\binom krr^n\,.\tag{$\ast\ast$}$$
Is there some clever way to manipulate the recurrence $(\ast)$ in order to obtain $(\ast\ast)$?
 A: To avoid further editing to the other answer, I give you some details on the closed form formula of the Bernoulli numbers. Note that the Stirling numbers of the second kind which ounts the number of nonempty partitions in sets of size $k$ of a size $n$ set can be given explicitly by an inclusion exclusion arguement $-$ by counting of surjective functions (this is the proof I know, and it is not much complicated) $-$ as $$\left\{\begin{matrix}n\\k\end{matrix}\right\}=\frac 1 {k!}\sum_{j=0}^k\binom kj(-1)^{j-k}j^n$$
Thus the formula is $$B_n=\sum_{k=0}^n \frac{(-1)^k}{k+1}k!\left\{\begin{matrix}n\\k\end{matrix}\right\}$$
Moreover, if we define the Bernoulli polynomials as $$B_n(x)=\sum_{k=0}^n\binom nk B_k x^{n-k}$$ so that $B_n(0)=B_n$ we have to see if it is possible to prove things like $$\Delta {B_n}\left( x \right) = n{x^{n - 1}}$$ $${B_n}\left( x \right) = \sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k + 1}}{\Delta ^n}{x^k}} $$ where $${\Delta ^n}{x^k} = \sum\limits_{j = 0}^n\binom nj {{{\left( { - 1} \right)}^{n - j}}{{\left( {x + j} \right)}^k}} $$
Note then that the special case $x=0$ gives the Stirling Number of the Second Kind, so $$B_n=B_n(0)=\sum_{k=0}^n \frac{(-1)^k}{k+1}k!\left\{\begin{matrix}n\\k\end{matrix}\right\}$$
is what you're after. Since EGFs have turned up, recall that the Bernoulli polynomials $B_n(t)$ have the exponential generating function $$\frac{ze^{tz}}{e^z-1}=\sum_{n\geqslant 0}B_n(t)\frac{z^n}{n!}$$
that is, using convolution,  $$B_n(t)=\sum_{k=0}^n\binom nk B_k t^{n-k}$$
On the other hand, the Stirling numbers arise as $$\frac{(e^z-1)^k}{k!}=\sum_{n\geqslant 0}\left\{\begin{matrix}n\\k\end{matrix}\right\} \frac{z^n}{n!}$$
Surely this can clean up a road for a proof.
