# How to simplify this combinatorial expression?

Find \begin{eqnarray} \sum_{j\in\mathbb{N}}(n-2j)^k\binom{n}{2j-m} \end{eqnarray}

Note that this question is a generalization of this one. I tried to imitate the steps in the answer given in that post but without success. Any idea?

• Take $(n-2i)^k$ outside the summation? – Hypergeometricx Aug 7 '15 at 16:02
• Out of curiosity, does $\mathbb{N}$ include zero? It seems in the original post, it does not. – parsiad Aug 7 '15 at 16:04
• To me zero is not a natural number. – No_way Aug 7 '15 at 16:07
• Why $2j-m$ in the binomial coefficient? The given link suggests $2j+m$ – andre Aug 8 '15 at 8:13
• Are $m$ and $k$ restricted to the integers? If so, you can take derivatives of a couple of binomial expansions to reduce to a sum of $k$ terms. – will Aug 15 '15 at 0:29

$\newcommand{\bbx}[1]{\,\bbox[15px,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_{j\ \in\ \mathbb{N}}\pars{n - 2j}^{\,k}\ {n \choose 2j - m} & = \sum_{j = 0}^{\infty}\pars{n - j}^{\,k}\ {n \choose j - m}{1 + \pars{-1}^{\,j} \over 2} = {\mrm{f}\pars{1} + \mrm{f}\pars{-1} \over 2}\label{1}\tag{1} \\[2mm] &\ \mbox{where}\ \,\mrm{f}\pars{x} \equiv \sum_{j = m}^{\infty}\pars{n - j}^{k}\ {n \choose j - m}x^{\,j} \end{align}
$\ds{\Large\mrm{f}\pars{-1}:\ ?.}$ \begin{align} \mrm{f}\pars{-1} & = k!\,\pars{-1}^{m}\oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1}} \pars{\expo{z} - 1}^{n}\,{\dd z \over 2\pi\ic} \end{align} The integral over $\ds{z}$ can be evaluated by using an identity which involves the Stirling Number of the Second Kind $\ds{a \brace b}$. Namely, $$\pars{\expo{z} - 1}^{s} = s!\sum_{j = 0}^{\infty}{j \brace s}{z^{\,j} \over j!} \label{2}\tag{2}$$ Then, \begin{align} \oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1}} \pars{\expo{z} - 1}^{s}\,{\dd z \over 2\pi\ic} & = s!\sum_{j = 0}^{\infty}{j \brace s}{1 \over j!} \oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1 - j}}\,{\dd z \over 2\pi\ic} \\[5mm] & = s!\sum_{j = 0}^{\infty}{j \brace s}{1 \over j!}\, {\pars{-m}^{k - j} \over \pars{k - j}!} \\[5mm] & = \bracks{k \geq s}{s! \over k!}\,\pars{-1}^{k}\,m^{k} \sum_{j = s}^{k}{j \brace s}{k \choose j}\,{\pars{-1}^{\,j} \over m^{\,j}} \label{3}\tag{3} \end{align} \begin{align} &\mbox{With this result,}\ \,\mrm{f}\pars{-1}\ \mbox{is given by} \\ &\bbx{\mrm{f}\pars{-1} = \bracks{k \geq n}\pars{-1}^{m + k}\,m^{k}\,n! \sum_{j = n}^{k}{j \brace n}{k \choose j}{\pars{-1}^{\,j} \over m^{\,j}}} \label{4}\tag{4} \end{align}
$\ds{\Large\mrm{f}\pars{1}:\ ?.}$ \begin{align} \mrm{f}\pars{1} & = k!\oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1}} \pars{\expo{z} + 1}^{n}\,{\dd z \over 2\pi\ic} = k!\oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1}} 2^{n}\pars{1 + {\expo{z} - 1 \over 2}}^{n}\,{\dd z \over 2\pi\ic} \\[5mm] & = k!\sum_{\ell = 0}^{n}{n \choose \ell} \oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1}} 2^{n}\pars{\expo{z} - 1 \over 2}^{n\ell}\,{\dd z \over 2\pi\ic} \\[5mm] & = k!\sum_{\ell = 0}^{n}{n \choose \ell}2^{\pars{1 - \ell}n} \oint_{\verts{z} = 1}{\expo{-mz} \over z^{k + 1}}\pars{\expo{z} - 1}^{n\ell} \,{\dd z \over 2\pi\ic} \end{align} With result \eqref{3}: \begin{align} &\mrm{f}\pars{1} = k!\sum_{\ell = 0}^{n}{n \choose \ell}2^{\pars{1 - \ell}n}\braces{% \bracks{k \geq n\ell}{\pars{n\ell}! \over k!}\,\pars{-1}^{k}\,m^{k} \sum_{j = n\ell}^{k}{j \brace n\ell}{k \choose j} \,{\pars{-1}^{\,j} \over m^{\,j}}} \\[5mm] & \bbx{\mrm{f}\pars{1} = \pars{-1}^{k}\,2^{n}\,m^{k}\sum_{\ell = 0}^{M}\sum_{j = n\ell}^{k} {n \choose \ell}{j \brace n\ell}{k \choose j}\pars{-1}^{\,j}\, {\pars{n\ell}! \over 2^{n\ell}m^{\,j}}}\label{5}\tag{5} \\ &\mbox{where}\quad M \equiv \min\braces{\left\lfloor\,{k \over n}\,\right\rfloor,n} \end{align}