A result of equation $y^2+1=x^p$ where $p$ is odd prime. Example 2.4.4 page 23 of the book "Problems of algebraic number theory" by R. Murty is about solving equation  $y^2+1=x^p$ where $p$ is odd prime and $x,y\in \mathbb{Z}$. Solving this example lead to two sum over some factorials which a special case of those is as follow:
$$\sum_{k=0}^{m}\frac{k^m}{k!(m-k)!}(-1)^{m-k}=1$$
I was interested to a small solution way to this.
 A: Hint:
Fix $m \geq 1$, and define the function $f\colon[0,\infty)\to \mathbb{R}$ defined by
$$
f(x) = (e^x-1)^m
$$
In particular, we have by the Binomial theorem that $$f(x) = \sum_{k=0}^m \binom{m}{k} e^{kx} (-1)^{m-k} = m! \sum_{k=0}^m \frac{1}{k!(m-k)!} e^{kx} (-1)^{m-k}.$$ 
Now, consider the $m$-th derivative $f^{(m)}$ of $f$, evaluated at $x=0$.
A: We get:
$$ \sum_{k=0}^{m}\binom{m}{k}k^m (-1)^{m-k} $$
by appying $\delta^m$ to the polynomial $p(x)=x^m$, where $\delta$ is the forward difference operator:
$$ (\delta p)(x) = p(x+1)-p(x). $$
If $p(x)$ is a polynomial with degree $\geq 1$, the degree of $(\delta p)(x)$ is just the degree of $p(x)$ minus one. Moreover, if $c_k x^k$ is the monomial with the highest degree in $p(x)$, the monomial with the highest degree in $(\delta p)(x)$ is $k c_k x^{k-1}$. It follows that if $p(x)=x^m$, then $(\delta^m p)(x) = m!$.
The claim easily follows.
A: I would begin by noticing that the denominator is exactly the denominator of $\binom{m}k$ and multiply the sum by $\frac{m!}{m!}$ to rewrite it as
$$\frac1{m!}\sum_{k=0}^m\binom{m}kk^m(-1)^{m-k}\;.$$
Thus, what you’re trying to prove is equivalent to
$$\sum_{k=0}^m\binom{m}kk^m(-1)^{m-k}=m!\;.\tag{1}$$
The sum looks very much like the sort that one typically gets in an inclusion-exclusion calculation, except that one would usually have $(-1)^k$ rather than $(-1)^{m-k}$. That’s easily arranged, however: let $\ell=m-k$, so that $k=m-\ell$. Since $\binom{m}k=\binom{m}{m-k}=\binom{m}\ell$, $(1)$ becomes
$$\sum_{\ell=0}^m\binom{m}\ell(-1)^\ell(m-\ell)^m=m!\;.$$
With practice you can do this without actually making a substitution using a new variable name and just go directly to
$$\sum_{k=0}^m\binom{m}k(-1)^k(m-k)^m=m!\;.\tag{2}$$
To prove $(2)$, we need only show that both sides count the same thing. On the one hand, $m!$ is the number of bijections from $[m]=\{1,\ldots,m\}$ to $[m]$. 
Now for each $i\in[m]$ let $A_i$ be the set of functions from $[m]$ to $[m]\setminus\{i\}$, i.e., the set of functions from $[m]$ to $[m]$ whose ranges do not contain $i$. If $\varnothing\ne F\subseteq[m]$, $\bigcap_{i\in F}A_i$ is the set of functions from $[m]$ to $[m]\setminus F$, and there are
$$\left|\bigcap_{i\in F}A_i\right|=(m-|F|)^m$$
such functions. The inclusion-exclusion principle then says that there are 
$$\left|\bigcup_{i\in[m]}A_i\right|=\sum_{\varnothing\ne F\subseteq[m]}(-1)^{|F|-1}(m-|F|)^m\tag{3}$$
functions from $[m]$ to $[m]$ that are not surjective. For $k=1,\ldots,n$ there are $\binom{m}k$ subsets of $[m]$ of cardinality $k$, so $(3)$ can be rewritten as
$$\left|\bigcup_{i\in[m]}A_i\right|=\sum_{k=1}^m\binom{m}k(-1)^{k-1}(m-k)^m\;.$$
Finally, there are $m^m$ functions from $[m]$ to $[m]$ altogether, so the number of them that are bijections is
$$\begin{align*}
m^m-\sum_{k=1}^m\binom{m}k(-1)^{k-1}(m-k)^m&=m^m+\sum_{k=1}^m\binom{m}k(-1)^k(m-k)^m\\
&=\sum_{k=0}^m\binom{m}k(-1)^k(m-k)^m\;,
\end{align*}$$
exactly as we wanted.
