Find the value of $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}. $$
Jul 23, 2020 #1 MountEvariste 87 0 Find the value of $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}. $$
Oct 16, 2020 #2 lfdahl Gold Member MHB 749 0 Spoiler: Suggested solution The answer is: $\sum_{k=0}^{n}(-1)^kk^n\binom{n}{k} = (-1)^nn!\;\;\;\;(1)$ In order to show the identity, we need the following lemma: $\sum_{k=0}^{n}(-1)^kk^m\binom{n}{k} = 0 , \, \, \, \, m = 0,1,.., n-1.\;\;\; (2)$ Proof by induction: Consider the binomial identity: $(1-x)^n =\sum_{j=0}^{n}\binom{n}{j}(-1)^jx^j \;\;\; (3)$ Case $m = 0$: Putting $x = 1$ in $(3)$ yields: $\sum_{j=0}^{n}\binom{n}{j}(-1)^j = 0$ Case $m = 1$: Differentiating $(3)$ once yields: $-n(1-x)^{n-1} =\sum_{j=0}^{n}\binom{n}{j}(-1)^jjx^{j-1}$ Again putting $x = 1$: $\sum_{j=0}^{n}\binom{n}{j}(-1)^jj = 0$. Assume the $m$th step is OK, where $1 \leq m < n-1$. We need to show, that our lemma also holds for step $m+1$: Differentiate $(3)$ $m+1$ times: $(-1)^{m+1}n(n-1)...(n-m)(1-x)^{n-m-1} = \sum_{j=0}^{n}\binom{n}{j}(-1)^jj(j-1)..(j-m)x^{j-m-1}$ Evaluating at $x = 1$: \[\sum_{j=0}^{n}\binom{n}{j}(-1)^j\left ( j^{m+1}+c_mj^m+c_{m-1}j^{m-1} + ... + c_1j\right )=0 \\ \\ \sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m+1} + c_m\sum_{j=0}^{n}\binom{n}{j}(-1)^jj^m +c_{m-1}\sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m-1}+...+c_1\sum_{j=0}^{n}\binom{n}{j}(-1)^jj =0 \\ \therefore \sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m+1} = 0.\] Now we are well prepared to prove, that $(1)$ holds. This will be another proof by induction: Let $S_n = \sum_{k=0}^{n}(-1)^kk^n\binom{n}{k}$. Then we have: $S_0 = 1 = (-1)^00!$, and $S_1 = (-1)^00^1\binom{1}{0}+(-1)^11^1\binom{1}{1} = -1 = (-1)^11!$ Therefore, we may assume, that $(1)$ holds for some step $ n > 1$: $S_n = (-1)^nn!$ \[S_{n+1} = \sum_{k=0}^{n+1}(-1)^kk^{n+1}\binom{n+1}{k} = \sum_{k=1}^{n+1}(-1)^kk^n\frac{(n+1)!}{(k-1)!(n+1-k)!}\\= \sum_{j=0}^{n}(-1)^{j+1}(j+1)^n\frac{(n+1)n!}{j!(n-j)!}= -(n+1)\sum_{j=0}^{n}(-1)^j(j+1)^n\binom{n}{j} \\= -(n+1)\sum_{j=0}^{n}(-1)^j\left ( 1+\binom{n}{1}j+\binom{n}{2}j^{2}+...+\binom{n}{n-1}j^{n-1}+j^n \right )\binom{n}{j} \\=-(n+1)\left ( \sum_{m=0}^{n-1}\binom{n}{m}\sum_{j=0}^{n}(-1)^jj^{m}\binom{n}{j}+S_n\right )\] With the help of our lemma, the double sum in the parenthesis equals 0, so we are left with: \[S_{n+1} = -(n+1)S_n = (-1)^{n+1}(n+1)! \;\;\; q.e.d.\] Last edited: Oct 16, 2020
Spoiler: Suggested solution The answer is: $\sum_{k=0}^{n}(-1)^kk^n\binom{n}{k} = (-1)^nn!\;\;\;\;(1)$ In order to show the identity, we need the following lemma: $\sum_{k=0}^{n}(-1)^kk^m\binom{n}{k} = 0 , \, \, \, \, m = 0,1,.., n-1.\;\;\; (2)$ Proof by induction: Consider the binomial identity: $(1-x)^n =\sum_{j=0}^{n}\binom{n}{j}(-1)^jx^j \;\;\; (3)$ Case $m = 0$: Putting $x = 1$ in $(3)$ yields: $\sum_{j=0}^{n}\binom{n}{j}(-1)^j = 0$ Case $m = 1$: Differentiating $(3)$ once yields: $-n(1-x)^{n-1} =\sum_{j=0}^{n}\binom{n}{j}(-1)^jjx^{j-1}$ Again putting $x = 1$: $\sum_{j=0}^{n}\binom{n}{j}(-1)^jj = 0$. Assume the $m$th step is OK, where $1 \leq m < n-1$. We need to show, that our lemma also holds for step $m+1$: Differentiate $(3)$ $m+1$ times: $(-1)^{m+1}n(n-1)...(n-m)(1-x)^{n-m-1} = \sum_{j=0}^{n}\binom{n}{j}(-1)^jj(j-1)..(j-m)x^{j-m-1}$ Evaluating at $x = 1$: \[\sum_{j=0}^{n}\binom{n}{j}(-1)^j\left ( j^{m+1}+c_mj^m+c_{m-1}j^{m-1} + ... + c_1j\right )=0 \\ \\ \sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m+1} + c_m\sum_{j=0}^{n}\binom{n}{j}(-1)^jj^m +c_{m-1}\sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m-1}+...+c_1\sum_{j=0}^{n}\binom{n}{j}(-1)^jj =0 \\ \therefore \sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m+1} = 0.\] Now we are well prepared to prove, that $(1)$ holds. This will be another proof by induction: Let $S_n = \sum_{k=0}^{n}(-1)^kk^n\binom{n}{k}$. Then we have: $S_0 = 1 = (-1)^00!$, and $S_1 = (-1)^00^1\binom{1}{0}+(-1)^11^1\binom{1}{1} = -1 = (-1)^11!$ Therefore, we may assume, that $(1)$ holds for some step $ n > 1$: $S_n = (-1)^nn!$ \[S_{n+1} = \sum_{k=0}^{n+1}(-1)^kk^{n+1}\binom{n+1}{k} = \sum_{k=1}^{n+1}(-1)^kk^n\frac{(n+1)!}{(k-1)!(n+1-k)!}\\= \sum_{j=0}^{n}(-1)^{j+1}(j+1)^n\frac{(n+1)n!}{j!(n-j)!}= -(n+1)\sum_{j=0}^{n}(-1)^j(j+1)^n\binom{n}{j} \\= -(n+1)\sum_{j=0}^{n}(-1)^j\left ( 1+\binom{n}{1}j+\binom{n}{2}j^{2}+...+\binom{n}{n-1}j^{n-1}+j^n \right )\binom{n}{j} \\=-(n+1)\left ( \sum_{m=0}^{n-1}\binom{n}{m}\sum_{j=0}^{n}(-1)^jj^{m}\binom{n}{j}+S_n\right )\] With the help of our lemma, the double sum in the parenthesis equals 0, so we are left with: \[S_{n+1} = -(n+1)S_n = (-1)^{n+1}(n+1)! \;\;\; q.e.d.\]