Skip to main content
MathOverflow

Return to Question

added 107 characters in body
Source Link
Martin Zhang
Martin Zhang
  • 183
  • 6

Question: let \begin{equation} c_n=\sum_{i=0}^n \sqrt{\binom{n}{i}}. \end{equation} How does $c_n$ grow with $n$?

My conjecture is that $c_n=\Theta(2^{0.5n}n^{0.25})$.This is because \begin{equation} 0.5^{0.5n} c_n = \sum_{i=0}^n \sqrt{\binom{n}{i}0.5^n}=\sum_{i=0}^n\sqrt{Pr(X=i)}, \end{equation} for $X\sim Bin(n,0.5)$. The binomial distribution $Bin(n,0.5)$ is approximately the normal distribution $N(0.5n, 0.25n)$. Also, if $Y\sim N(0.5n, 0.25n)$, it is not hard to see that \begin{equation} \int \sqrt{f(y)} dy =\Theta(n^{0.25}). \end{equation} Therefore I believe that it is also true that $0.5^{0.5n} c_n=\Theta(n^{0.25})$. I played with matlab to get some evidence and found that \begin{equation} \frac{0.5^{0.5n} c_n}{n^{0.25}} \approx \frac{\pi}{2}, \end{equation} for $n=100,1000,10000,100000,1000000$. So the conjecture should be true. So anyone can prove it?

(It turns out that $\frac{0.5^{0.5n} c_n}{n^{0.25}} \approx (2\pi)^{0.25}$ instead of $\frac{\pi}{2}$).

Question: let \begin{equation} c_n=\sum_{i=0}^n \sqrt{\binom{n}{i}}. \end{equation} How does $c_n$ grow with $n$?

My conjecture is that $c_n=\Theta(2^{0.5n}n^{0.25})$.This is because \begin{equation} 0.5^{0.5n} c_n = \sum_{i=0}^n \sqrt{\binom{n}{i}0.5^n}=\sum_{i=0}^n\sqrt{Pr(X=i)}, \end{equation} for $X\sim Bin(n,0.5)$. The binomial distribution $Bin(n,0.5)$ is approximately the normal distribution $N(0.5n, 0.25n)$. Also, if $Y\sim N(0.5n, 0.25n)$, it is not hard to see that \begin{equation} \int \sqrt{f(y)} dy =\Theta(n^{0.25}). \end{equation} Therefore I believe that it is also true that $0.5^{0.5n} c_n=\Theta(n^{0.25})$. I played with matlab to get some evidence and found that \begin{equation} \frac{0.5^{0.5n} c_n}{n^{0.25}} \approx \frac{\pi}{2}, \end{equation} for $n=100,1000,10000,100000,1000000$. So the conjecture should be true. So anyone can prove it?

Question: let \begin{equation} c_n=\sum_{i=0}^n \sqrt{\binom{n}{i}}. \end{equation} How does $c_n$ grow with $n$?

My conjecture is that $c_n=\Theta(2^{0.5n}n^{0.25})$.This is because \begin{equation} 0.5^{0.5n} c_n = \sum_{i=0}^n \sqrt{\binom{n}{i}0.5^n}=\sum_{i=0}^n\sqrt{Pr(X=i)}, \end{equation} for $X\sim Bin(n,0.5)$. The binomial distribution $Bin(n,0.5)$ is approximately the normal distribution $N(0.5n, 0.25n)$. Also, if $Y\sim N(0.5n, 0.25n)$, it is not hard to see that \begin{equation} \int \sqrt{f(y)} dy =\Theta(n^{0.25}). \end{equation} Therefore I believe that it is also true that $0.5^{0.5n} c_n=\Theta(n^{0.25})$. I played with matlab to get some evidence and found that \begin{equation} \frac{0.5^{0.5n} c_n}{n^{0.25}} \approx \frac{\pi}{2}, \end{equation} for $n=100,1000,10000,100000,1000000$. So the conjecture should be true. So anyone can prove it?

(It turns out that $\frac{0.5^{0.5n} c_n}{n^{0.25}} \approx (2\pi)^{0.25}$ instead of $\frac{\pi}{2}$).

Source Link
Martin Zhang
Martin Zhang
  • 183
  • 6

Sum of square roots of binomial coefficients

Question: let \begin{equation} c_n=\sum_{i=0}^n \sqrt{\binom{n}{i}}. \end{equation} How does $c_n$ grow with $n$?

My conjecture is that $c_n=\Theta(2^{0.5n}n^{0.25})$.This is because \begin{equation} 0.5^{0.5n} c_n = \sum_{i=0}^n \sqrt{\binom{n}{i}0.5^n}=\sum_{i=0}^n\sqrt{Pr(X=i)}, \end{equation} for $X\sim Bin(n,0.5)$. The binomial distribution $Bin(n,0.5)$ is approximately the normal distribution $N(0.5n, 0.25n)$. Also, if $Y\sim N(0.5n, 0.25n)$, it is not hard to see that \begin{equation} \int \sqrt{f(y)} dy =\Theta(n^{0.25}). \end{equation} Therefore I believe that it is also true that $0.5^{0.5n} c_n=\Theta(n^{0.25})$. I played with matlab to get some evidence and found that \begin{equation} \frac{0.5^{0.5n} c_n}{n^{0.25}} \approx \frac{\pi}{2}, \end{equation} for $n=100,1000,10000,100000,1000000$. So the conjecture should be true. So anyone can prove it?