TAOCP 5.1.3 Exercise 4
**Corrected Solution to Exercise 5.
Exercise 4. [**] [M21] What is the value of $\sum_k (-1)^k \left{ {n \atop k} \right} k! \binom{-7}{k}$ ?
Verified: no
Solve time: 1h11m
Corrected Solution to Exercise 5.1.3.4, Part 4
We are asked to evaluate
$$ \sum_{k=0}^n (-1)^k \left{ {n \atop k} \right} k! \binom{-7}{k}. $$
Let us proceed carefully.
Step 1: Use the standard identity for negative binomial coefficients
For any integer $m\ge 0$,
$$ \binom{-m}{k} = (-1)^k \binom{m+k-1}{k}. $$
With $m=7$, we have
$$ \binom{-7}{k} = (-1)^k \binom{k+6}{k}. $$
Therefore, in the sum,
$$ (-1)^k \binom{-7}{k} = (-1)^k \cdot (-1)^k \binom{k+6}{k} = \binom{k+6}{k}. $$
Hence the sum simplifies to
$$ \sum_{k=0}^n \left{ {n \atop k} \right} k! \binom{k+6}{k}. $$
Step 2: Rewrite $\binom{k+6}{k}$ using factorials
$$ \binom{k+6}{k} = \frac{(k+6)!}{6! , k!}. $$
Multiplying by $k!$ from the sum, we get
$$ k! \binom{k+6}{k} = k! \cdot \frac{(k+6)!}{6! , k!} = \frac{(k+6)!}{6!}. $$
So the sum becomes
$$ \sum_{k=0}^n \left{ {n \atop k} \right} \frac{(k+6)!}{6!}. $$
Step 3: Apply the standard Stirling-number identity
A standard identity for Stirling numbers of the second kind is
$$ \sum_{k=0}^n \left{ {n \atop k} \right} k! \binom{r}{k} = r^n, $$
valid for arbitrary integer $r$. To match this form, note that
$$ \binom{r}{k} k! = r (r-1) \cdots (r-k+1) = (r)_k, $$
the falling factorial. In our sum, we have
$$ k! \binom{k+6}{k} = (6+1)(6+2)\cdots (6+k) = (k+1)(k+2)\cdots (k+6), $$
which is equivalent to
$$ (-1)^6 (-6)_k = (-1)^6 (-6)(-5)\cdots(-6+k-1) = (-6)_k, $$
but it is simpler to use the inversion formula approach.
Step 4: Use the Stirling-number inversion formula
The formula
$$ \sum_{k=0}^n \left{ {n \atop k} \right} k! \binom{r}{k} = r^n $$
applies for arbitrary $r$. In our sum, if we set $r=-7$, then
$$ \sum_{k=0}^n \left{ {n \atop k} \right} k! \binom{-7}{k} = (-7)^n. $$
The original sum contains an extra factor $(-1)^k$. Using Step 1, we absorb this factor into the binomial:
$$ (-1)^k \binom{-7}{k} = \binom{k+6}{k}. $$
Hence the sum becomes exactly
$$ \sum_{k=0}^n \left{ {n \atop k} \right} k! \binom{k+6}{k}. $$
By the Stirling-number identity with $r=7$ (since $\binom{k+6}{k} k! = (k+6)!/6! = 7 \cdot 8 \cdots (k+6)$ is the rising factorial), we get
$$ \sum_{k=0}^n \left{ {n \atop k} \right} k! \binom{k+6}{k} = 7^n. $$
Step 5: Conclusion
Therefore, the value of the original sum is
$$ \boxed{7^n}. $$
This is a finite, closed-form evaluation. The generating-function manipulations in the previous solution are correct but unnecessary; the intended evaluation is immediate from the Stirling-number identity.
Final Answer
$$ \sum_{k=0}^n (-1)^k \left{ {n \atop k} \right} k! \binom{-7}{k} = 7^n. $$