How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Question

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$

This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion?

Answer 1

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

Thus

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

Also, by C-S

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

thus

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