What's the best bound for $\sum_{i=0}^{[\lg{n}]}{\binom{n}{2^{i}}}$ I want to find best lower bound and upper bound for:
$$\sum_{i=0}^{[\lg{n}]}{\binom{n}{2^{i}}}$$
 A: As @JackD'Aurizio states, the sum is dominated by the choices of $i$ for which $2^i$ is closest to $\frac{n}{2}$.  Let $a = \left\lfloor \lg \frac{n}{2} \right\rfloor = \lfloor \lg n \rfloor - 1$.  This gives the largest $i$ for which $2^i \le \frac{n}{2}$.  The terms we should focus on are then $i = a$ and $i = a + 1$.
(To see that the other terms are insignificant, observe $\binom{n}{r-1} = \frac{r}{n-r} \binom{n}{r} \le \frac12 \binom{n}{r}$, provided $r \le \frac{n}{3}$.  Moreover, since $\frac{n}{4} < 2^a \le \frac{n}{2}$, we have at least $\frac{n}{12}$ values of $r$ for which $2^{a-1} < r \le \frac{n}{3}$.  Thus for each of the summands with $i < a$, we have
$$ \binom{n}{2^i} \le \binom{n}{2^{a-1}} = \binom{n}{2^a} \prod_{r = 2^{a-1} + 1}^{2^a} \frac{\binom{n}{r-1}}{\binom{n}{r}} \le 2^{- n/12 } \binom{n}{2^a}. $$
Hence the sum $\sum_{i < a} \binom{n}{2^i} < \lg n \cdot 2^{- n / 12} \binom{n}{2^a}$ is exponentially small compared to $\binom{n}{2^a}$.)
Now note that we have $a = \lfloor \lg n \rfloor - 1 = \lg n - \{ \lg n \} - 1$, where for $x \in \mathbb{R}$, $\{ x\}$ is the fractional part of $x$.  Hence $2^a = 2^{\lg n - \{ \lg n \} - 1} = cn$, where $c = 2^{ - \{ \lg n \} - 1 }$.  We also have $2^{a+1} = 2cn$.
Now, using Stirling's Approximation, when $k, n \rightarrow \infty$, one has
$$ \binom{n}{k} \sim \sqrt{ \frac{n}{2 \pi k (n-k) } } \left( \frac{n}{k} \right)^k \left( \frac{n }{n-k} \right)^{n-k}. $$
When $k = \gamma n$, for some $\gamma \in (0,1)$, this simplifies to
$$ \binom{n}{\gamma n} \sim \left( 2 \pi \gamma (1 - \gamma) n \right)^{- 1/2} \left( \gamma^{\gamma} (1 - \gamma)^{1 - \gamma} \right)^{-n}.$$
Putting everything together, it follows that
$$ \sum_{i=0}^{\lfloor \lg n \rfloor} \binom{n}{2^i} \sim \left( 2 \pi c (1 - c) n \right)^{- 1/2} \left( c^c (1 - c)^{1 - c} \right)^{-n} + \left( 4 \pi c (1 - 2c) n \right)^{- 1/2} \left( (2c)^{2c} (1 - 2c)^{1 - 2c} \right)^{-n},$$
where $c = 2^{ - \{ \lg n \} - 1}$.
Now of course that is a horrible expression.  What is more useful is to compare this to $2^n$.  The binary entropy $H(x)$ is defined by $H(x) = -x \lg x - (1-x) \lg (1 - x)$.  Then the term $ \left( c^c (1-c)^{1-c} \right)^{-n} = 2^{H(c) n}$, and similarly the other term is $2^{H(2c)n}$.  The leading square root factors are insignificant compared to these exponential terms.  Hence we find that the order of magnitude of the sum is given by
$$ \sum_{i=0}^{\lfloor \lg n \rfloor} \binom{n}{2^i} = \Theta \left( n^{-1/2} 2^{ f(n) n } \right), $$
where $f(n) = \max \left( H(c), H(2c) \right)$, where $c = 2^{- \{ \lg n \} - 1}$.
Below is a graph showing the values $f(n)$ takes as $\{ \lg n \}$ ranges from $0$ to $1$ (thanks, WolframAlpha!):

So you can see when $\{ \lg n \} \approx 0,1$ (that is, when $n$ is close to a power of $2$), we can get $2^i \approx \frac{n}{2}$, which means the order of magnitude is roughly $2^n / \sqrt{n}$.  This is not too far from the trivial upper bound of $2^n$.
On the other hand, for more moderate values of $\{ \lg n \}$ (that is, when $n$ is far from a power of $2$), the constant in the exponent drops.  The minimum constant is achieved when $\{ \lg n \} \approx 0.585$, when $2^a \approx \frac{n}{3}$ and $2^{a+1} \approx \frac{2n}{3}$ are both simultaneously as far from $\frac{n}{2}$ as possible.  Here the sum is of the order of magnitude roughly $2^{0.918n} / \sqrt{n}$, which is of course exponentially smaller than $2^n$.
[Sorry I can't give a more elegant answer, but these binomial calculations usually require getting your hands dirty.]
