<s>[INST] proving an invloved combinatorial identity How to prove following Identity?
$$\sum_{k=0}^n (-1)^k {n-k \choose k} m^k (m+1)^{n-2k} = \frac {m^{n+1}-1}{m-1}, m \ge 2$$
This seems very hard to me. Any idea about how to prove it combinatorialy?
[P.S: for $k > \lfloor {\frac n 2}\rfloor$ L.H.S evaluates to $0$. ]
 [/INST] This is not a combinatorial proof but I still find it rather nice. Let us replace $m$ by $x$ to get a more general polynomial identity.
We can notice that
\begin{equation*}
(-1)^{k} \binom{n-k}{k} x^{k}(x+1)^{n-2k}
\end{equation*}
is the coefficient of $y^{k}$ in $(1+x-xy)^{n-k}$. Consequently the left hand of the identity is the coefficient of $y^{n}$ in
\begin{equation*}
\sum_{k=0}^{n} (y+xy-xy^{2})^{n-k}=\sum_{k=0}^{n} (y+xy-xy^{2})^{k}.
\end{equation*}
For $k > n$, $(y+xy-xy^{2})^{k}$ makes no contribution to the coefficient of $y^{n}$, so we can extend the summation to infinity. Hence the left hand side equals
\begin{equation*}
\frac{1}{n!} \frac{\partial}{\partial^{n} y} \frac{1}{1-y-xy+xy^{2}}
\end{equation*}
evaluated in $y=0$. We have
\begin{align}
\enspace &\frac{1}{n!} \frac{\partial}{\partial^{n} y} \frac{1}{1-y-xy+xy^{2}}\\
= \enspace & \frac{1}{n!}\frac{\partial}{\partial^{n} y} \left(\frac{1}{1-y} \frac{1}{1-xy}\right) \\
= \enspace & \frac{1}{n!} \sum_{k=0}^{n} \binom{n}{k}\left(\frac{\partial}{\partial^{k} y}\frac{1}{1-y}\right)\left(\frac{\partial}{\partial^{n-k} y} \frac{1}{1-xy}\right)
\end{align}
But
\begin{align*}
&\frac{\partial}{\partial^{k} y}\frac{1}{1-y}=\frac{k!}{(1-y)^{k+1}} \\
&\frac{\partial}{\partial^{k} y}\frac{1}{1-xy}=\frac{x^{k}k!}{(1-xy)^{k+1}}.
\end{align*}
When $y=0$ the denominators become $1$ and the numerators simplifly with the binomial coefficient, so that indeed the left hand side equals $\displaystyle\sum_{k=0}^{n}x^{k}$.
</s>