6
$\begingroup$

I find the following formula to be true $$ \sum_{k=0}^n {{n}\choose{k}}(k+1)^n(-1)^k=(-1)^nn! $$ at least for $n=1,2,3$, could any one give a proof about this in general? I'm almost sure it is true, because I use a different method to compare with a known result (in fact something of much higher level and in a very different field, the author said the result without proof, and I deduce that that result comes down to the above formula), for which I want to give an alternative proof. A good reference about this formula is preferred. I guess there should be a more general formula for which this is a special case. Thanks!

$\endgroup$
  • $\begingroup$ If it were $k^n$ instead of $(k+1)^n$, I would have said inclusion-exclusion method for counting bijections $\{1,\cdots,n\}\to\{1,\cdots,n\}$ in terms of counting functions $\{1,\cdots,k\}\to\{1,\cdots,n\}$. $\endgroup$ – arctic tern May 21 '17 at 5:14
7
$\begingroup$

If $f(x)\in R [x]$ is a polynomial over a unital ring $R$ and the degree of $f(x)$ is at most $n$, then $$\sum_{k=0}^n\,(-1)^{n-k}\,\binom{n}{k}\,f(x+k)=n!\,a_n\,,$$ where $a_n$ is the coefficient of the $n$-th degree term of $f(x)$. To show this, try to compute $\Delta^n\,f(x)$, where $\Delta$ is the forward differencing operator: $$\Delta\,g(x):=g(x+1)-g(x)\,,$$ for $g(x)\in R[x]$. The easiest way is probably induction on $n$, noting that (1) $\Delta$ decreases the degree and (2) $\Delta^n\,f(x)=\Delta^{n-1}\,\left(\Delta\,f(x)\right)$.

$\endgroup$
  • $\begingroup$ Thanks a lot, that's very cool! $\endgroup$ – Lao-tzu May 20 '17 at 21:48
  • 1
    $\begingroup$ Indeed, writing the shift operator $Sf(x)=f(x+1)$, we have $\Delta^n=(S-I)^n$ which may be expanded with the binomial theorem... $\endgroup$ – arctic tern May 21 '17 at 5:15
3
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\sum_{k = 0}^{n}{n \choose k}\pars{k + 1}^{n}\pars{-1}^{k} = \sum_{k = 0}^{n}{n \choose k}\pars{-1}^{k}\ \overbrace{\bracks{n!\oint_{\verts{z} = 1}{\expo{\pars{k + 1}z} \over z^{n + 1}}\,{\dd z \over 2\pi\ic}}}^{\ds{\pars{k + 1}^{n}}} \\[5mm] = &\ n!\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1}} \sum_{k = 0}^{n}{n \choose k}\pars{-\expo{z}}^{k}\,{\dd z \over 2\pi\ic} = n!\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1}} \pars{1 - \expo{z}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] = &\ \pars{-1}^{n}\,n!\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1}}\ \overbrace{\pars{\expo{z} - 1}^{n}} ^{\ds{n!\sum_{k = 0}^{\infty}{k \brace n}{z^{k} \over k!}}}\ \,{\dd z \over 2\pi\ic}\,,\qquad \pars{\substack{\ds{i \brace j}\ \mbox{is a} \\[1mm] {\large Stirling\ Number\ of\ the\ Second\ Kind}}} \\[5mm] = &\ \pars{-1}^{n}\,\pars{n!}^{2}\sum_{k = 0}^{\infty}\!\!{k \brace n}{1 \over k!}\ \overbrace{\oint_{\verts{z} = 1}{\expo{z} \over z^{n + 1 - k}}\,{\dd z \over 2\pi\ic}}^{\ds{1 \over \pars{n - k}!}} = \pars{-1}^{n}\,\pars{n!}^{2}{n \brace n}{1 \over n!} = \bbx{\pars{-1}^{n}\,n!} \end{align}

Reference: Stirling Number of the Second Kind.

$\endgroup$
2
$\begingroup$

Stirling Numbers of the Second Kind have the following relation: $$ \newcommand{\stirtwo}[2]{\left\{#1\atop#2\right\}} \begin{align} (k+1)^n &=\sum_{j=0}^n\stirtwo{n}{j}\binom{k+1}{j}\,j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}\left[\binom{k}{j}+\binom{k}{j-1}\right]j!\\ \end{align} $$ Therefore, $$ \begin{align} \sum_{k=0}^n\binom{n}{k}(k+1)^n(-1)^k &=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{j=0}^n\stirtwo{n}{j}\left[\binom{k}{j}+\binom{k}{j-1}\right]j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}\sum_{k=0}^n(-1)^k\binom{n}{k}\left[\binom{k}{j}+\binom{k}{j-1}\right]j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}\sum_{k=0}^n(-1)^k\left[\binom{n}{j}\binom{n-j}{k-j}+\binom{n}{j-1}\binom{n-j+1}{k-j+1}\right]j!\\ &=\sum_{j=0}^n\stirtwo{n}{j}(-1)^n\big([j=n]+[j=n+1]\big)\,j!\\[9pt] &=(-1)^nn! \end{align} $$ since $\stirtwo{n}{n}=1$, and for $j\gt n$, $\stirtwo{n}{j}=0$.

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