Cómo evaluar $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Question

Podemos encontrar $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$

Este problema me preguntó mi amigo hace aproximadamente un año, pero yo no sabía cómo atacar el problema. Ahora, estoy interesada en la solución. Alguna sugerencia?

Answer 1

Aquí es una aproximación asintótica en lugar de una evaluación.

Si tomamos la primera diferencia del logaritmo de $\sqrt{\binom{n}{k}}$, obtenemos $$ \frac12\log\left(\frac{n-k+1}{k}\right)\etiqueta{1} $$ que se desvanece al $k\sim n/2$.

Si tomamos la segunda diferencia de la de registro de $\sqrt{\binom{n}{k}}$, obtenemos $$ \frac12\log\left(\frac{k-1}{k}\right)-\frac12\log\left(\frac{n-k+2}{n-k+1}\right)\sim-\frac1{2k}-\frac1{2(n-k+1)}\tag{2} $$ Esto es aproximadamente el $$ -\frac2n\etiqueta{3} $$ donde la primera diferencia se desvanece.

La aproximación de la suma por una Gaussiana, da el valor de la suma a ser asintótica $$ \begin{align} \overbrace{\sqrt{\textstyle\binom{n}{n/2}}}^{\begin{array}{c}\text{account}\\\text{for the}\\\text{maximum}\end{array}}\cdot\overbrace{\int_{-\infty}^\infty e^{-x^2/n}\,\mathrm{d}x}^{\begin{array}{c}\text{account}\\\text{for second}\\\text{difference}\end{array}} &\sim2^{n/2}\left(\frac2{\pi n}\right)^{1/4}\cdot\sqrt{\pi n}\\ Y=2^{n/2}(2\pi n)^{1/4}\etiqueta{4} \end{align} $$ Para $n=100$, la suma es $5.62976892\times10^{15}$ $(4)$ da $5.63695737\times10^{15}$.

Para $n=1000$, la suma es $2.91399232\times10^{151}$ $(4)$ da $2.91435733\times10^{151}$.

Como $n$ se hace más grande, la aproximación se pone mejor.

Answer 2

$$\left(\sum_{k=0}^{n} \sqrt{\binom{n}{k}} \right)^2 \geq \sum_{k=0}^{n} \binom{n}{k}=2^n$$

Así

$$\sum_{k=0}^{n} \sqrt{\binom{n}{k}} \geq 2^{\frac{n}{2}}$$

También, a través de la C-S

$$\left(\sum_{k=0}^{n} \sqrt{\binom{n}{k}} \right)^2 \leq (n+1)2^n$$

así

$$\sum_{k=0}^{n} \sqrt{\binom{n}{k}}\leq 2^{\frac{n}{2}} \sqrt{n+1}$$

Answer 3

Para cualquier potencia positiva $p$, $\displaystyle \sum\limits_{k=1}^{n} \binom{n}{k}^p \sim \dfrac{2^{np}}{\sqrt{p}}\cdot\left(\frac{n\pi}{2}\right)^{(1-p)/2} $,

De decisiones, $n \mapsto 2n$,

Tenemos, $\displaystyle \dfrac{\binom{2n}{n-k}}{\binom{2n}{n}} = \dfrac{n}{n+k}\prod\limits_{j=1}^{k-1}\dfrac{1-\frac{j}{n}}{1+\frac{j}{n}} = \dfrac{n}{n+k}e^{\sum\limits_{j=1}^{k-1}\log\frac{1-j/n}{1+j/n}}$

y la forma de expansión de taylor en $t=0$, $\log \dfrac{1-t}{1+t} = -2t - \dfrac{2x^3}{3}+O(t^5)$,

por eso,$0 < -2t - \log\dfrac{1-t}{1+t} = O(t^3) $, $0 < t < 1/2$.

Es sufices a mirar a la central de $n^{2/3}$-términos,

desde, $\displaystyle \dfrac{\binom{2n}{n-k}}{\binom{2n}{n}} = \dfrac{n}{n+k}\large{e^{\sum\limits_{j=1}^{k-1}\log\frac{1-j/n}{1+j/n}}}$ $ = \begin{cases}(1+O(n^{-1/3}))e^{-k^2/n} & \textrm{ for } k\le n^{2/3} \\ O(e^{-n^{1/3}}) & \textrm{ for } k>n^{2/3}\end{cases}$

Por lo tanto, $\displaystyle \sum_{k=1}^{n-1} \dfrac{\binom{2n}{n-k}^p}{\binom{2n}{n}^p} = (1+O(n^{-1/3}))\sum\limits_{k=1}^{n^{2/3}} e^{-pk^2/n} + o(1) = (1+O(n^{-1/3}))\int_1^{n^{2/3}} e^{-pt^2/n}\,dt + O(1)$

$$\sim \frac{1}{2}\sqrt{\dfrac{n\pi}{p}}$$

Usando la Aproximación de Stirling tenemos, $\displaystyle \binom{2n}{n} \sim \dfrac{4^{n}}{\sqrt{n\pi}}$

Por lo tanto, $\displaystyle \sum\limits_{k=1}^{n} \binom{n}{k}^p \sim \dfrac{2^{np}}{\sqrt{p}}\cdot\left(\frac{n\pi}{2}\right)^{(1-p)/2} $