Fórmula $\sum_{k=0}^n k^d {n \choose 2k}$

Question

Si $d \geq 1$ es un número entero, hay una fórmula general para $$\sum_{k=0}^n k^d {n \choose 2k}\,?$ $

Sabemos que $\sum_{k=0}^n k {n \choose 2k} = \frac{n2^n}{8}$ y $\sum_{k=0}^n k^2 {n \choose 2k} = \frac{n(n+1)2^n}{32}$.

Tenga en cuenta que ${n \choose 2k} = 0$ cuando $2k > n$.

Answer 1

La definición de la ecuación para los números de Stirling del segundo tipoes $$ \sum_{k=0}^n\left\{n\cima de k\right\}\binom{x}{k}k!=x^n $$ Por lo tanto, debido a que $$ \sum_{k=0}^n\binom{m}{n-2k}=2^{m-1}\left(1+\color{#C00000}{(-1)^n[m=0]}\right) $$ tenemos $$ \begin{align} \sum_{k=0}^nk^d\binom{n}{2k} &=2^{-d}\sum_{k=0}^n\sum_{j=0}^d\left\{d\atop j\right\}\binom{2k}{j}j!\binom{n}{2k}\\ &=2^{-d}\sum_{j=0}^d\sum_{k=0}^n\left\{d\atop j\right\}\binom{n}{j}j!\binom{n-j}{n-2k}\\ &=2^{-d}\sum_{j=0}^d\left\{d\atop j\right\}\binom{n}{j}j!\,2^{n-j-1}+\color{#C00000}{(-1)^n2^{-d-1}\left\{d\atop n\right\}n!}\\ &=2^{n-d-1}\left[\sum_{j=0}^d\left\{d\atop j\right\}\binom{n}{j}\frac{j!}{2^j}+\color{#C00000}{(-1)^n\left\{d\atop n\right\}\frac{n!}{2^n}}\right] \end{align} $$ Cuando $n\gt d$, $\left\{d\atop n\right\}=0$, por lo tanto, el $\color{#C00000}{\text{correction term}}$ desaparece para $n\gt d$.

---

Ejemplos

Para $d=1$, obtenemos $$ \sum_{k=0}^nk\binom{n}{2k}=2^{n-3}n+\color{#C00000}{(-1)^n\left\{1\cima n\right\}\frac{n!}{4}} $$ Para $d=2$, obtenemos $$ \begin{align} \sum_{k=0}^nk^2\binom{n}{2k} &=2^{n-3}\left(\binom{n}{1}1!\,2^{-1}+\binom{n}{2}2!\,2^{-2}\right)+(-1)^n\frac18\left\{2\atop n\right\}n!\\ &=2^{n-5}n(n+1)+\color{#C00000}{(-1)^n\left\{2\atop n\right\}\frac{n!}{8}} \end{align} $$

---

Código de Mathematica

f[d_]:=Evaluate[
  2^(#-d-1)Together[Expand[FunctionExpand[
    Sum[StirlingS2[d,j]Binomial[#,j]j!/2^j,{j,0,d}]]]]
    +(-1)^# StirlingS2[d,#]#!/2^(d+1)]&

A continuación, f[3][n]rendimientos $$ 2^{n-7}\left(n^3+3n^2\right)+\color{#C00000}{(-1)^n\left\{3\cima n\right\}\frac{n!}{16}} $$ y f[7][n]rendimientos $$ 2^{n-15}\left(n^7+21n^6+105n^5+35n^4-210n^3+112n^2\right)+\color{#C00000}{(-1)^n\left\{7\cima n\right\}\frac{n!}{256}} $$

Answer 2

Llame a su suma $f_n.$ Siguiente Wilf presentamos la generación de la función $$F(z) = \sum_{n\ge 0} f_n z^n = \sum_{n\ge 0} z^n \sum_{k=0}^n k^d {n\elegir 2k} = \sum_{n\ge 0} z^n \sum_{k=0}^{\lfloor n/2\rfloor} k^d {n\elegir 2k}.$$

Vamos a extraer la forma cerrada como el coeficiente de $[z^n] F(z).$ Ahora, el truco es el intercambio de sumatorias, llegar $$F(z) = \sum_{k\ge 0} k^d \sum_{n\ge 2k} {n\elegir 2k} z^n = \sum_{k\ge 0} k^d \sum_{n\ge 0} {n+2k\elegir 2k} z^{n+2k} \\= \sum_{k\ge 0} k^d z^{2k} \sum_{n\ge 0} {n+2k\elegir 2k} z^n = \sum_{k\ge 0} k^d z^{2k} \frac{1}{(1-z)^{2k+1}} \\ = \frac{1}{1-z} \sum_{k\ge 0} k^d \left(\frac{z^2}{(1-z)^2}\right)^k.$$

Ahora observar que $$\sum_{q\ge 0} p^d z^q = \frac{1}{(1-z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\cima de p\right\rangle z^{p+1}$$ donde hemos introducido Euleriano números.

Esto implica que $$F(z) = \frac{1}{1-z} \frac{1}{(1-z^2/(1-z)^2)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\cima de p\right\rangle \left(\frac{z^2}{(1-z)^2}\right)^{p+1}.$$ Este es $$\frac{1}{1-z} \frac{(1-z)^{2d+2}}{(1-2z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\cima de p\right\rangle \left(\frac{z^2}{(1-z)^2}\right)^{p+1} \\ = \frac{1}{1-z} \frac{(1-z)^{2d+2}}{(1-2z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\cima de p\right\rangle z^{2p+2} (1-z)^{-2p-2} \\= \frac{1}{(1-2z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\cima de p\right\rangle z^{2p+2} (1-z)^{2d-2p-1}.$$ La extracción de los coeficientes de (necesitamos $[z^n] F(z)$) obtenemos $$\sum_{q=0}^n {n-q+d\elegir d} 2^{n-q} \sum_{p=0}^{d-1} \left\langle d\cima de p\right\rangle [z^q] z^{2p+2} (1-z)^{2d-2p-1}.$$ Teniendo en cuenta que el grado del polinomio en el interior de la suma vemos que para un no-cero de la contribución que debe tener $$q\ge 2p+2 \quad\text{and}\quad q\le 2d+1.$$ Por lo tanto, nos limitamos a $n\ge 2d+1$ $p\le (q-2)/2$ para obtener $$\sum_{q=2}^{2d+1} {n-q+d\elegir d} 2^{n-q} \sum_{p=0}^{\lfloor (p-2)/2\rfloor} \left\langle d\cima de p\right\rangle [z^q] z^{2p+2} (1-z)^{2d-2p-1} \\ = \sum_{q=2}^{2d+1} {n-q+d\elegir d} 2^{n-q} \sum_{p=0}^{\lfloor (p-2)/2\rfloor} \left\langle d\cima de p\right\rangle [z^{p-2 p-2}] (1-z)^{2d-2p-1} \\ = 2^n \sum_{q=2}^{2d+1} {n-q+d\elegir d} 2^{-q} \sum_{p=0}^{\lfloor (p-2)/2\rfloor} \left\langle d\cima de p\right\rangle (-1)^{p-2 p-2} {2d-2p-1\elegir p-2 p-2}.$$

Ahora la observación clave en este punto es que el número de términos en la suma no depende del $n$, pero sólo en $d.$

Esto significa que podemos obtener de una forma cerrada mediante la evaluación de la $2d$ términos en la suma.

Obtenemos $d=2$ la fórmula $${2}^{n} \left( 1/4\,{n\elegir 2}-3/8\,{n-1\elegir 2} +1/4\,{n-2\elegir 2}-1/16\,{n-3\elegir 2} \right)$$ que se simplifica a $$\frac{1}{32} \,{2}^{n}\;n \left( n+1 \right).$$ Para $d=3$ tenemos $${2}^{n} \left( 1/4\,{n+1\elegir 3}-5/8\,{n\elegir 3} +{\frac {7}{8}}\,{n-1\elegir 3}\\-{\frac {11}{16}}\,{n-2\elegir 3}+{\frac {9}{32}}\,{n-3\elegir 3}-{\frac {3}{64}}\,{n-4\elegir 3} \right)$$ que es $${\frac {1}{128}}\,{2}^{n}{n}^{2} \left( n+3 \right),$$ y así sucesivamente.

El último ejemplo que voy a presentar aquí es$d=7$, lo que da $${2}^{n} \left( 1/4\,{n+5\elegir 7}-{\frac {13}{8}}\,{n+4\elegir 7} +{\frac {99}{8}}\,{n+3\elegir 7}-{\frac {803}{16}}\,{n+2 \elegir 7}\\+{\frac {4253}{32}}\,{n+1\elegir 7} -{\frac {15903}{64}}\,{n\elegir 7}+{\frac {5413}{16}}\,{n-1\elegir 7}-{\frac { 5441}{16}}\,{n-2\elegir 7}\\+{\frac {8085}{32}}\,{n-3\elegir 7} -{\frac {4389}{32}}\,{n-4\elegir 7}+{\frac {13545}{256}}\,{n-5 \elegir 7}-{\frac {7035}{512}}\,{n-6\elegir 7} \\+{\frac {2205}{1024}}\,{n-7\elegir 7}-{\frac {315}{2048}}\,{n-8\elegir 7} \right)$$ que es $${\frac {1}{32768}}\,{2}^{n}{n}^{2} \left( {n}^{5}+21\,{n}^{4} +105\,{n}^{3}+35\,{n}^{2}-210\,n+112 \right).$$ La aparente patrón en el OP que la forma cerrada es un múltiplo de $${n+d-1\choose d}$$ no se sostiene.

La conclusión de la observación. Viendo el esfuerzo de arriba parece casi seguro que una solución más elegante usando Zeilberger / Hermana Celine puede ser encontrado. En mis experimentos ha aparecido, sin embargo, que el último método produce recurrencias que tienen un número de términos que no es lineal en $d$. El lector puede que desee comparar la asignación de los recursos de la telescópico frente a la cerrada la fórmula anterior.

Answer 3

Esta es una respuesta medio. Tenemos

$$(1+x)^{n}=x^{0}\binom{n}{0}+x^{1}\binom{n}{1}....+x^{n}\binom{n}{n}$$

Si tomamos derivado de este con respecto a x.

$$n(1+x)^{n-1}=1x^{0}\binom{n}{1}+2x^{1}\binom{n}{1}....+nx^{n-1}\binom{n}{n}$$

$x=1$ Tenemos %#% $ #%

Ahora si multiplican la ecuación antes con x y derivado otra vez.

$$n2^{n-1}=1\binom{n}{1}+2\binom{n}{2}....+n\binom{n}{n}$$

For $$n(1+x)^{n-1}+n(n-1)(1+x)^{n-2}=1^2x^{0}\binom{n}{1}+2^2x^{1}\binom{n}{1}....+n^2x^{n-1}\binom{n}{n}$ $x=1$$

Concluimos por inducción que

$$n2^{n-1}+n(n-1)2^{n-2}=1^2\binom{n}{1}+2^2\binom{n}{2}....+n^2\binom{n}{n}$$

No sé qué hacer.

Answer 4

$\newcommand{\+}{^{\daga}} \newcommand{\ángulos}[1]{\left\langle\, nº 1 \,\right\rangle} \newcommand{\llaves}[1]{\left\lbrace\, nº 1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, nº 1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, nº 1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\piso}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\mitad}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\a la derecha\vert\,} \newcommand{\cy}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left (\, nº 1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\vphantom{\large Un}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, nº 1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $\ds{\sum_{k = 0}^{n}k^{d}{n \choose 2k}:\ {\large ?}.\quad d \geq 1.\quad}$ Vamos a suponer que $\ds{d \in {\mathbb N}}$.

$$ \media\bracks{\pars{1 + \raíz{x}}^{n} + \pars{1 - \raíz{x}}^{n}} =\sum_{k = 0}^{n}{n \elegir 2k}x^{k} $$

$$ \sum_{k = 0}^{n}k^{d}{n \elegir 2k}x^{k} = \pars{x\,\partiald{}{x}}^{d}\llaves{\media\bracks{\pars{1 + \raíz{x}}^{n} + \pars{1 - \raíz{x}}^{n}}} $$

$$ \sum_{k = 0}^{n}k^{d}{n \elegir 2k} = \media\,\lim_{x \to 1}\pars{x\,\partiald{}{x}}^{d}\bracks{\pars{1 + \raíz{x}}^{n} + \pars{1 - \raíz{x}}^{n}} $$

Con $\ds{\ln\pars{x} \equiv t\quad\imp\quad x = \expo{t}}$: \begin{align} \sum_{k = 0}^{n}k^{d}{n \choose 2k} &= \half\,\lim_{t \to 0}\partiald[d]{}{t} \bracks{\pars{1 + \expo{t/2}}^{n} + \pars{1 - \expo{t/2}}^{n}} \\[3mm]&= 2^{n - 1}\lim_{t \to 0}\partiald[d]{}{t}\braces{\expo{nt/4} \bracks{\cosh^{n}\pars{t \over 4} + \pars{-1}^{n}\sinh^{n}\pars{t \over 4}}} \end{align}

Answer 5

Primero observa esto

$$ \sum_{k=0}^{n} {n\choose 2k} = 1/2 \sum_{k=0}^{n} {n\choose k}. $$

Entonces aquí es una técnica.