6
$\begingroup$

I'm trying to prove the following:

For every $n \ge 5$: $$\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$$

I've tried cancelling one $(n-k)$, and got this: $$n\sum_{k=0}^{n-1}{n-1\choose k}\left(-1\right)^k\left(n-k\right)^3 = 0$$

I've also tried expressing the first formula as such: $$\sum_{k=0}^na_kb_k$$ Where $a_k = {n \choose k}\left(-1\right)^k$ and $b_k = \left(n-k\right)^4 = \sum_{j=0}^4{4\choose j}n^j\left(-k\right)^{4-j}$

It's easy to see that $\sum_{k=0}^n a_k = \left(1-1\right)^n = 0$ by the binomial theorem.

But I'm lost as to why this work only for n>=5. What am I missing?

$\endgroup$
2
  • $\begingroup$ Any idea to start could be to consider the derivative of $(X-1)^n$ at $1$, evaluated in two different ways as you did for $(X-1)^n$. And to continue from there. I am not sure if this works though; it is merely an idea. $\endgroup$
    – quid
    Dec 26 '14 at 12:59
  • $\begingroup$ I thought of that, but not sure how this would get me to the required $\left(n-k\right)^4$... $\endgroup$
    – hyit
    Dec 26 '14 at 13:01
6
$\begingroup$

The expression counts the number of ways to partition a set of $4$ elements into $n$ distinguishable non-empty cells, which certainly must give zero for $n \geq 5$.

The result follows by inclusion exclusion. Alternately, see Stirling numbers of the second kind for a more general view.

$\endgroup$
4
  • $\begingroup$ Perfect! So is this the correct way of thinking? Let $A = \{a, b, c, d\}$ so that $|A| = 4$, and let $B = \{1, ..., n\}$ so that $|B| = n$. So we're looking for $|\{f: A -> B: f is injective\}|$. Total number of functions from A to B is $n^4$. Let Sk be defined as $S_k = |\{f: A -> B\\\{k\}\}|$? $\endgroup$
    – hyit
    Dec 26 '14 at 13:56
  • 1
    $\begingroup$ @hyit You look to be on the right track, except that you might have meant surjective. $\endgroup$ Dec 26 '14 at 14:20
  • $\begingroup$ But surjective doesn't mean that the partition is distinct, does it? $\endgroup$
    – hyit
    Dec 26 '14 at 14:30
  • $\begingroup$ @hyit Ah, I made an error: distinguishable, not distinct. By phrasing the problem with functions on four elements, you automatically get this. What you don't automatically get is non-emptiness of partitions, which surjectivity provides. $\endgroup$ Dec 26 '14 at 14:54
5
$\begingroup$

$p(k)=k^4$ is a fourth degree polynomial. Let $\delta$ be the backward difference operator: $$ \delta f(x) = f(x)-f(x-1).$$ Since the degree of $\delta f$ is one less than the degree of $f$, for any $n\geq 5$ we have $\delta^n p(x) = 0$.

$\endgroup$
4
  • $\begingroup$ This is the result of the first equation in my answer. I thought that it required a bit more justification. Perhaps I was wrong :-) BTW, the operator in the question is the backward difference operator. $\endgroup$
    – robjohn
    Dec 26 '14 at 19:47
  • $\begingroup$ @robjohn: I always have some little problem about the nomenclature (especially because it looked natural to me to use the substitution $k\to n-k$), but the conclusion still holds by replacing the backward difference with the forward difference. $\endgroup$ Dec 26 '14 at 22:24
  • $\begingroup$ I was just mentioning in case you wanted to change $\delta f(x)=f(x)-f(x-1)$ to match the question. I wasn't saying that your answer was insufficient. $\endgroup$
    – robjohn
    Dec 26 '14 at 22:48
  • $\begingroup$ @robjohn: I know, I know. Anyway, now it is fixed. $\endgroup$ Dec 27 '14 at 0:37
3
$\begingroup$

The idea of cancelling the factors of $n-k$ should work. $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m &=n\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^{m-1}\\ &-n\sum_{k=0}^n(-1)^k\binom{n-1}{k-1}(n-k)^{m-1}\\ &=n\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}(n-k)^{m-1}\\ \end{align} $$ For $m\le n$, induction yields $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m &=\frac{n!}{(n-m)!}\sum_{k=0}^{n-m}(-1)^k\binom{n-m}{k}\\ &=\frac{n!}{(n-m)!}(1-1)^{n-m}\\ &=\left\{ \begin{array}{} n!&\text{if }m=n\\ 0&\text{if }m\lt n \end{array} \right. \end{align} $$


A Second Approach

In this answer there are three proofs of $$ \begin{align} \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} &=\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\\ &=[n=k] \end{align} $$ where $[\dots]$ are Iverson Brackets. Furthermore, $\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}$ $$ \sum_{k=0}^m\binom{n}{k}\,\stirtwo{m}{k}k!=n^m $$ where $\stirtwo{m}{k}$ are Stirling Numbers of the Second Kind. Therefore, $$ \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(x-k)^m &=\sum_{k=0}^n\sum_{j=0}^m(-1)^{k-j}\binom{n}{k}\binom{m}{j}x^{m-j}k^j\\ &=\sum_{k=0}^n\sum_{j=0}^m\sum_{i=0}^j(-1)^{k-j}\binom{n}{k}\binom{m}{j}x^{m-j}\binom{k}{i}\stirtwo{j}{i}i!\\ &=\sum_{j=0}^m\sum_{i=0}^j(-1)^{n-j}\binom{m}{j}x^{m-j}\,[n=i]\,\stirtwo{j}{i}i!\\ &=\sum_{j=0}^m(-1)^{n-j}\binom{m}{j}x^{m-j}\stirtwo{j}{n}n! \end{align} $$ If $m\lt n$, then either $\binom{m}{j}=0$ or $\stirtwo{j}{n}=0$. If $m=n$, the only non-zero term is $j=m$.

$\endgroup$
4
  • $\begingroup$ Amazing! Doesn't this assume that $0^0 = 0$? Also, I know $\sum_{k=0}^n \left(-1\right)^k {n\choose k} = \left(1-1\right)^n$, but how did you get the greater formula? $\endgroup$
    – hyit
    Dec 26 '14 at 13:29
  • $\begingroup$ @hyit: it is just the binomial theorem; expand $(1-1)^{n-m}$ $\endgroup$
    – robjohn
    Dec 26 '14 at 13:31
  • $\begingroup$ Then you just multiplied both parts of the equation by $\frac{n!}{\left(n-m\right)!}$ ? $\endgroup$
    – hyit
    Dec 26 '14 at 13:44
  • $\begingroup$ @hyit: yes; so that it matches the formula gotten by induction. $\endgroup$
    – robjohn
    Dec 26 '14 at 13:52
1
$\begingroup$

Hint: Let $j=n-k$ be the new iterator, and use $\displaystyle{n\choose k}={n\choose n-k}$. You will arrive at a slightly simpler expression. To evaluate it, expand $(1+x)^n$, and differentiate both sides with regard to x, then multiply both sides by x. Repeat these two steps four times. Lastly, set $x=-1$.

$\endgroup$
0
$\begingroup$

It will be useful to know:

$\mathbf{ Theorem.}$ Let $p(x)= a_0+a_1x+\cdots +a_nx^n$ be $\mathit{any}$ polynomial in $\mathbb{C}[x]$ (of degree $\leq n$), then

$$ \sum_{k} {n\choose k}(-1)^k p(k)=(-1)^n n! a_n.$$ So in particular when $p$ has degree<n, then such sums are $0$.

Proof: see Graham, Knuth, Patashnik, Concrete Mathematics, Addison Wesley, 1989 , formula (5.42). (As was suggested above the proof is by using difference operators. ) $\Box$

Concerning the original question, since $x\mapsto (n-x)^4$ is of degree 4 in $x$ but $n\geq 5 $ we get 0.

$\endgroup$
0
$\begingroup$

Consider the sum

$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^q$$

where $q\ge 0.$ This is

$$q! [z^q] \sum_{k=0}^n {n\choose k} (-1)^k \exp((n-k)z).$$

We obtain

$$q! [z^q] \exp(nz) \sum_{k=0}^n {n\choose k} (-1)^k \exp(-kz) \\ = q! [z^q] \exp(nz) (1-\exp(-z))^n \\ = q! [z^q] (\exp(z)-1)^n.$$

Now since $(\exp(z)-1)^n = z^n + \cdots$ this is zero when $q\lt n$ and we have the claim. Observe that the EGF here yields $n! \times {q\brace n}.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.