11
$\begingroup$

When trying to answer this question I arrived at $$\int^\infty_0\frac{\sin(nx)\sin^n{x}}{x^{n+1}}dx=\frac{\pi}{2}\frac{(-1)^n}{n!}\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$$ After using Wolfram Alpha to evaluate the sum for several values of $n$, it seems that $$\sum^n_{k=0}(-1)^k\binom{n}{k}k^n\stackrel?=(-1)^nn!$$ The best I can do is to express the sum as $$\left(x\frac{d}{dx}\right)^n(1-x)^n\Bigg{|}_{x=1}$$ but that is as far as I can go. May I know how one can compute the sum? Thanks.

$\endgroup$
8
$\begingroup$

Suppose that I want to count the permutations of the set $[n]=\{1,\ldots,n\}$. For each $k\in[n]$ let $A_k$ be the set of functions from $[n]$ to $[n]\setminus\{k\}$. A function from $[n]$ to $[n]$ is a permutation iff it is not in $A_1\cup\ldots\cup A_n$, so there are $n^n-|A_1\cup\ldots\cup A_n|$ permutations. By a standard inclusion-exclusion argument

$$\begin{align*} |A_1\cup\ldots\cup A_n|&=\sum_{1\le k\le n}|A_k|\\ &\quad-\sum_{1\le k<\ell\le n}|A_k\cap A_\ell|\\ &\quad+\sum_{1\le j<k<\ell\le n}|A_j\cap A_k\cap A_\ell|\\ &\quad\;\vdots\\ &\quad+(-1)^{n+1}|A_1\cap\ldots\cap A_n|\;. \end{align*}\tag{1}$$

Let $K\subseteq[n]$, and let $k=|K|$. Then

$$\left|\bigcap_{i\in K}A_i\right|=(n-k)^n\;,$$

because $\bigcap_{i\in K}A_i$ is the set of functions from $[n]$ to $[n]$ whose ranges are disjoint from $K$. There are $\binom{n}k$ such sets $K$, so $(1)$ can be rewritten

$$\begin{align*} |A_1\cup\ldots\cup A_n|&=\binom{n}1(n-1)^n\\ &\quad-\binom{n}2(n-2)^n\\ &\quad+\binom{n}3(n-3)^n\\ &\quad\;\vdots\\ &\quad+(-1)^{n+1}\binom{n}n(n-n)^n\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^n\;. \end{align*}$$

Of course we know that the number of permutations of $[n]$ is $n!$, so

$$\begin{align*} n!&=n^n-\sum_{k=1}^n(-1)^{k+1}\binom{n}k(n-k)^n\\ &=n^n+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)^n\\ &=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\\ &=\sum_{k=0}^n(-1)^k\binom{n}{n-k}(n-k)^n\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^n\\ &=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}kk^n\;, \end{align*}$$

and multiplication by $(-1)^n$ yields the desired result.

$\endgroup$
12
$\begingroup$

You can derive the result using the sum you get.

Let $x = e^\theta$, we have

$$ \left.\left(x\frac{d}{dx}\right)^n(1-x)^n\right|_{x=1} = \left.\frac{d^n}{d\theta^n}\left(1-e^\theta\right)^n\right|_{\theta=0} = (-1)^n \left.\frac{d^n}{d\theta^n}\left[\theta^n\left(\frac{e^\theta-1}{\theta}\right)^n\right]\right|_{\theta=0} $$ Recall the General Leibniz rule for the $n^{th}$ derivative for a product of two functions:

$$(fg)^{(n)} = \sum_{k=0}^n \binom{n}{k} f^{(k)} g^{(n-k)}$$ If one substitute $$f = \theta^n \quad\text{ and }\quad g = \begin{cases} \left(\frac{e^\theta-1}{\theta}\right)^n,&\theta \ne 0\\ 1, & \theta = 0 \end{cases} $$ and notice

  • $f^{(m)}(0) = 0$ for $m = 0, 1, \ldots, n-1$,
  • $g(\theta)$ is a smooth function over a neighborhood of $\theta = 0$.

We find under the General Leibniz rule, only the $k = n$ term survive and

$$\text{RHS} = (-1)^n \binom{n}{n} \left.\left( \frac{d^n}{d\theta^n}\theta^n \right)\right|_{\theta=0} g(0) = (-1)^n n! $$

$\endgroup$
  • 3
    $\begingroup$ This is my favorite answer. The change of variable technique is very clever. It makes sense of connections between recursion and series definitions for various special functions which I hadn't figured out before. $\endgroup$ – Cameron Williams Dec 26 '14 at 6:29
7
$\begingroup$

Another approach is to recognise $\sum^n_{k=0}(-1)^k\binom{n}{k}k^n$ as the result of taking the sequence $(i^n)_{i\in\Bbb N}$ of $n$-th powers, applying $n$ times $-\Delta$, where $\Delta$ is the difference operator $(a_i)_{i\in\Bbb N}\mapsto(a_{i+1}-a_i)_{i\in\Bbb N}$, and then taking the initial term at $i=0$. For the difference operator applied to polynomial sequences it is convenient to use the basis of so called falling factorial powers defined by $$ x^{\underline k} = x(x-1)\ldots(x-k+1) $$ which satisfy $\Delta\bigl((i^{\underline k})_{i\in\Bbb N}\bigr)=k(i^{\underline{ k-1}})_{i\in\Bbb N}$ for $k>0$, and $\Delta\bigl((i^{\underline 0})_{i\in\Bbb N}\bigr)=\Delta\bigl((1)_{i\in\Bbb N}\bigr)=0$. Since $x^{\underline k}$ is a monic polynomial of degree $k$ in $x$, it is clear that expressing the sequence $(i^n)_{i\in\Bbb N}$ as linear combination of falling factorial power sequences $(i^{\underline k})_{i\in\Bbb N}$ for $k=0,1,\ldots,n$ will involve the final sequence $(i^{\underline n})_{i\in\Bbb N}$ with coefficient$~1$. All other terms are killed by $\Delta^n$, so $\Delta^n\bigl((i^n)_{i\in\Bbb N}\bigr)=\Delta^n\bigl((i^{\underline n})_{i\in\Bbb N}\bigr)$, which by the above relations is the constant sequence $(n!i^{\underline 0})_{i\in\Bbb N}=(n!)_{i\in\Bbb N}$. It then follows that $$ \sum^n_{k=0}(-1)^k\binom{n}{k}k^n = (-\Delta)^n\bigl((i^n)_{i\in\Bbb N}\bigr)\Bigm|_{i=0} =(-1)^n n!. $$

$\endgroup$
  • $\begingroup$ Neat application of finite calculus. It's one of my favorite cute veins of mathematics. $\endgroup$ – Cameron Williams Dec 26 '14 at 6:26
4
$\begingroup$

Here is a contribution using basic complex variables.

Suppose we are trying to show that $$\sum_{k=0}^n {n\choose k} (-1)^k k^n = (-1)^n n!$$

Observe that $$k^n = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(kz) \; dz.$$

This gives for the sum the integral $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \sum_{k=0}^n {n\choose k} (-1)^k \exp(kz) \; dz$$ which is $$\frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1-\exp(z))^n \; dz.$$

But we have $$1-\exp(z) = - \frac{z}{1!} - \frac{z^2}{2!} - \frac{z^3}{3!} - \cdots$$ (starts at $z$ with no constant term) so the only term that contributes to the coefficient $[z^n] (1-\exp(z))^n$ is the product of the $n$ initial terms.

The coefficient on these is $-1,$ giving the final answer $$(-1)^n n!$$

$\endgroup$
  • $\begingroup$ Yes, I have used it many times in my posts, see for example this MSE link. $\endgroup$ – Marko Riedel Sep 9 '16 at 2:29
  • $\begingroup$ +1. This answer is a nice job. I just check the link ( a prolific answer, by the way ). $\endgroup$ – Felix Marin Sep 9 '16 at 2:55
  • $\begingroup$ @FelixMarin The following MSE link may interest you, note however that the OP is asking for a combinatorial proof. $\endgroup$ – Marko Riedel Sep 15 '16 at 22:37
2
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

There is a 'surprising' result of Borwein & Borwein: \begin{equation} \int_{0}^{\infty}\prod_{k = 0}^{n}{\sin\pars{a_{k}x} \over x}\,\dd x = {\pi \over 2}\prod_{k = 1}^{n}a_{k}\,,\qquad a_{k} \in \mathbb{R}\,,\quad a_{0} \geq \sum_{k = 1}^{n}\verts{a_{k}} \end{equation}

With $\ds{\quad a_{0} = n\quad\mbox{and}\quad a_{1} = a_{2} = \cdots = a_{n} = 1}$, we'll have $\ds{a_{0} = n = \sum_{k = 1}^{n}a_{k}}$ such that \begin{align} \color{#f00}{\int_{0}^{\infty} {\sin\pars{nx}\sin^{n}\pars{x} \over x^{n + 1}}\,\dd x} & = \int_{0}^{\infty}{\sin\pars{nx} \over x}\,\ \overbrace{{\sin\pars{x} \over x} \,{\sin\pars{x} \over x}\ldots{\sin\pars{x} \over x}} ^{\ds{n\ \mbox{terms}}}\ \,\dd x \\[5mm] & = {\pi \over 2}\prod_{k = 1}^{n}1 = \color{#f00}{\pi \over 2} \end{align}

$\endgroup$
  • $\begingroup$ Nice solution! (+1) $\endgroup$ – Markus Scheuer Sep 9 '16 at 19:03
  • 1
    $\begingroup$ @MarkusScheuer Thanks. Indeed, the identity is a 'surprising' one. $\endgroup$ – Felix Marin Sep 9 '16 at 20:03
1
$\begingroup$

Using inclusion-exclusion principle. Indeed, let $F$ be the set of all functions from $\{1,2,...,n\}$ into $\{1,2,...,n\}$. And let $A_{k}$ be the set of all $f \in F$ such that $k \notin \text{image}(f)$

$\endgroup$
1
$\begingroup$

The sum indeed evaluates to $(-1)^nn!$ and here is one possible derivation. In the (final) expression you got in the question, you can substitute $y=x-1$, and observe that for any function $f$ one has $\def\d{\mathrm d}\frac\d{\d x}f(x-1)=f'(x-1)$, which is the result of setting $y=x-1$ in $\frac\d{\d y}f(y)$; then you need to find $$ c_n=\left.\left((y+1)\circ\frac\d{\d y}\right)^n((-y)^n)\right|_{y=0}. $$ The operator $E=(y+1)\circ\frac\d{\d y}$ satisfies $E(y^k)=ky^k+ky^{k-1}$, from which one easily proves by induction that $E^m(y^k)|_{y=0}=0$ whenever $k>m$. Now one computes $$ c_n = E^n\bigl((-y)^n\bigr)|_{y=0} = E^{n-1}\Bigl(n(-y)^n)-n(-y)^{n-1}\Bigr)|_{y=0} = -nE^{n-1}\bigl((-y)^{n-1}\bigr)|_{y=0}=-nc_{n-1} $$ from which $c_n=(-1)^nn!$ follows by induction.

$\endgroup$
1
$\begingroup$

It is convenient to use the coefficient of operator $[t^k]$ to denote the coefficient of $t^k$ in a series. This way we can write e.g. \begin{align*} [t^k](1+t)^n=\binom{n}{k}\qquad\text{and}\qquad n![t^n]e^{kt}=k^n \end{align*}

We obtain \begin{align*} \sum_{k=0}^n(-1)^k\binom{n}{k}k^n&=\sum_{k=0}^\infty(-1)^k[u^k](1+u)^nn![t^n]e^{kt}\tag{1}\\ &=n![t^n]\sum_{k=0}^\infty\left(-e^t\right)^k[u^k](1+u)^n\tag{2}\\ &=n![t^n](1-e^t)^n\tag{3}\\ &=(-1)^nn!\tag{4} \end{align*} and the claim follows.

Comment:

  • In (1) we apply the coefficient of operator twice. We also extend the upper range of the series to $\infty$ without changing anything since we are adding zeros only.

  • In (2) we do some rearrangements and use the linearity of the coefficient of operator.

  • In (3) we use the substitution rule of the coefficient of operator with $u=-e^t$ \begin{align*} A(t)=\sum_{k=0}^\infty a_kt^k=\sum_{k=0}^\infty t^k[u^k]A(u) \end{align*}

  • In (4) we select the coefficient of $t^n$ from $(1-e^t)^n=(t-\frac{t^2}{2!}\pm\cdots)^n$.

$\endgroup$
1
$\begingroup$

It is a partial case ($x=0$) of the Tepper's identity $$ \sum^n_{k=0}(-1)^k\binom{n}{k}(x-k)^n=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.