Prove this binomial sum by induction

Question

Can someone help me with this one? Prove by mathematical induction

For $$n\geq1$$ $$\displaystyle{\sum^n_ {k=0} k^n\binom{n}{k}(-1)^k= (-1)^nn!}$$

It's easy to see that for $$n=1$$ $$\displaystyle{0^1\binom{1}{0}(-1)^0+1^1\binom{1}{1}(-1)^1= -1}$$ and $$\displaystyle{(-1)^11!=-1}$$

My problem is how to use the induction hypothesis I'm trying to solve it this way:

Perhaps I just have to add this to my sum: $${\sum_{k={n+1}}^{n+1}} (n+1)^{n+1}\binom {n+1}{n+1}(-1)^{n+1} $$ And get: $$\displaystyle{\sum^n_ {k=0} \biggl[k^n\binom{n}{k}(-1)^k}\biggr]+(n+1)^{n+1}\binom {n+1}{n+1}(-1)^{n+1}$$ And as: $$\displaystyle{\sum^n_ {k=0} k^n\binom{n}{k}(-1)^k= (-1)^nn!}$$ Then i get: $$\displaystyle{(-1)^nn!+(n+1)^{n+1}(-1)^{n+1}}$$ I tried this: $$\left(-1\right)^{n}\,n!+\left(-n-1\right)\,\left(n+1\right)^{n}\, \left(-1\right)^{n}$$ And this: $$\left(-1\right)^{n}\,\left(n!-n\,\left(n+1\right)^{n}-\left(n+1 \right)^{n}\right)$$ But i can't figure out how to get to this: $$\displaystyle{ (-1)^{n+1}(n+1)!}$$

What you have written down is nothing near what $\sum_{k=0}^{n+1}k^n\binom{n}{k}(-1)^k$ looks like, nor is it equal to $(-1)^{n+1}n+1!$. I think it would be whise to ask yourself: "what does the $\sum$-operator do?/How does it work?" — gebruiker, May 19 '14 at 14:23
Yes that looks a lot better. I would suggest you make an edit to your question such that it says what you just wrote... — gebruiker, May 19 '14 at 14:57

score 0 · Answer 1 · answered May 19 '14 at 14:51

$\quad~$ Hint: Start with the famous $\displaystyle\sum_{k=0}^n{n\choose k}x^k=(1+x)^n$, then differentiate, and multiply with x. Repeat the process a few times, and see what happens. Deduce and prove by induction the formula that should be pretty evident by now, and then let the number of repeated differentiations followed by multiplications be n, and x be $-1$. QED.

Prove this binomial sum by induction

1 Answers1