# Calculating $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$

• MHB
• MountEvariste
In summary, the formula for calculating the sum of terms $$(-1)^k k^n \binom{n}{k}$$ for all values of k from 0 to n is $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k} = 0$$ if n is even, and $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k} = (-1)^{\frac{n+1}{2}} n!$$ if n is odd. This notation represents the sum of these terms and the alternating signs help to account for overcounting and undercounting. The formula can be simplified using properties of
MountEvariste
Find the value of $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}.$$

$\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:

## 1. What is the purpose of calculating $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$?

The purpose of this calculation is to find the sum of the alternating binomial coefficients raised to the power of n multiplied by k. This sum has various applications in mathematics and statistics, including in the study of probability and combinatorics.

## 2. How is the summation formula for $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$ derived?

The summation formula is derived using the binomial theorem and the principle of inclusion-exclusion. This involves expanding the binomial coefficient and then using the alternating signs to cancel out certain terms, resulting in a simplified summation formula.

## 3. What are the possible values for n in the summation formula $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$?

The possible values for n are non-negative integers, as the binomial coefficient and the power of k are only defined for non-negative integers. However, the summation formula can also be extended to include other values of n, such as fractions or negative integers, using mathematical techniques.

## 4. Can the summation formula for $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$ be simplified?

Yes, the summation formula can be simplified in certain cases. For example, when n is an even integer, the summation will only have one term with a positive coefficient, resulting in a simplified formula. Additionally, when n is a multiple of 4, the summation will have a simpler closed form expression involving factorials.

## 5. What are some real-world applications of the summation formula for $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$?

The summation formula has applications in various fields, such as in the analysis of algorithms, where it can be used to calculate the expected running time of certain algorithms. It is also used in probability theory to calculate the probability of certain events occurring. In addition, the formula has applications in combinatorics, where it can be used to count the number of ways to choose and arrange objects in a given set.

• General Math
Replies
14
Views
1K
• General Math
Replies
1
Views
2K
• General Math
Replies
8
Views
2K
• General Math
Replies
2
Views
1K
• General Math
Replies
4
Views
1K
• Precalculus Mathematics Homework Help
Replies
11
Views
492
• General Math
Replies
1
Views
796
• General Math
Replies
3
Views
919
• General Math
Replies
8
Views
1K
• General Math
Replies
1
Views
2K