An upper bound for $\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$? Does anyone know of a reasonable upper bound for the following:
$$\sum_{i = 1}^m \frac{\binom{i}{k}}{2^i},$$
where we $k$ and $m$ are fixed positive integers, and we assume that $\binom{i}{k} = 0$ whenever $k > i$.
One trivial upper bound uses the identity $\binom{i}{k} \le \binom{i}{\frac i2}$, and the fact that $\binom{i}{\frac{i}{2}} \le \frac{2^{i+1}}{\sqrt{i}}$, to give a bound of 
$$2\sum_{i = 1}^m \frac{1}{\sqrt{i}},$$
where $\sum_{i = 1}^m \frac{1}{\sqrt{i}}$ is upper bounded by $2\sqrt{m}$, resulting in a bound of $4\sqrt{m}$. Can we do better?
Thanks!
Yair
 A: Yes you can do better. In fact
$$
  \sum_{i=k}^m \binom{i}{k} 2^{-i} \leq 2
$$
and this bound is sharp if $k$ is fixed and $m \to \infty$.
To see this, consider the function $x^{k} (1 - x)^{-(k+1)}$ near $0$; this has a power series expansion
$$
  \frac{x^k}{(1 - x)^{k+1}} = x^k \left( \sum_{\ell \geq 0} x^\ell \right)^{k+1} = \sum_{\ell \geq 0} \binom{k + \ell}{k} x^{\ell + k},
$$
(see here) which, after changing the sum to start at $k$ rather than $0$, is equal to
$$
  \sum_{i \geq k} \binom{i}{k} x^i.
$$
Now you can evaluate this function at $x = \frac12$ which gives
$$
  2^{-k} 2^{k+1} = \sum_{i \geq k} \binom{i}{k} 2^{-i}.
$$
Your series is a truncation of this sum, and so since each term is positive this gives an upper bound. Sharpness comes from taking $m \to \infty$, of course.
You can improve this bound if you know that $m$ is not much larger than $k$. Here is one estimate in the case when $m = k + O(k/\log k)$. Then,
$$
  \sum_{i = k}^m \binom{i}{k} 2^{-i} \leq \sum_{i=k}^m i^{i-k} 2^{-i} = \sum_{i=k}^m e^{(i - k) \log i} 2^{-i}
$$
This series will be dominated by a geometric series $c^{-i}$ for any $1 < c < 2$ as long as the exponent $(i - k) \log i = O(i)$, where the implied constant depends on $c$. This in turn is satisfied by the requirement $m - k = O(k/\log k)$, (or $k > m - O(\frac{m}{\log(m)}$). Specifically, for any $\varepsilon > 0$ such that $e^\varepsilon < 2$, if $m \le k+ \frac{\varepsilon k}{\log(k)}$ or $k \ge m - \frac{\varepsilon m}{\log m}$, the argument goes through.
Therefore, for any $1 < c < 2$ we have
$$
  \sum_{i = k}^m \binom{i}{k} 2^{-k} \leq \sum_{i=k}^m c^{-i} = O(c^{-k})
$$
if $m = k + O(k/\log k)$, where the implied constant depends on $c$.
A: I like Pot's argument better, but here's another approach for those who may be interested.

I get an upper bound of $2$, independent of $k$ and $m$.  
Applying summation by parts, we have, for $k \geq 2$,
$$\begin{align*}
\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} &= \binom{m}{k} \sum_{i=1}^m \frac{1}{2^i} - \sum_{i=1}^{m-1} \left(\binom{i+1}{k} - \binom{i}{k}\right) \sum_{j=1}^i \frac{1}{2^j} \\
&= \binom{m}{k} \left(1 - \frac{1}{2^m}\right) - \sum_{i=1}^{m-1} \binom{i}{k-1} \left(1 - \frac{1}{2^i}\right)\\
&= \binom{m}{k} - \binom{m}{k}\frac{1}{2^m} - \sum_{i=1}^{m-1} \binom{i}{k-1} + \sum_{i=1}^{n-1} \binom{i}{k-1} \frac{1}{2^i}\\
&= \binom{m}{k} - \binom{m}{k}\frac{1}{2^m} - \binom{m}{k} + \sum_{i=1}^{m-1} \binom{i}{k-1} \frac{1}{2^i}\\
&= \sum_{i=1}^{m-1} \binom{i}{k-1} \frac{1}{2^i}- \binom{m}{k}\frac{1}{2^m},
\end{align*}$$
where, in the second-to-last step, we use the upper summation identity for the binomial coefficients, $\displaystyle \sum_{i=0}^m \binom{i}{k} = \binom{m+1}{k+1}$. 
Letting $\displaystyle F(m,k) = \sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i}$, this means we have the recurrence $$F(m,k) = F(m-1,k-1) - \binom{m}{k}\frac{1}{2^m},$$ valid for $k \geq 2$.
Unrolling the recurrence is easy, and with $F(m-k+1,1) = 2 - \frac{m-k}{2^{m-k+1}} - \frac{3}{2^{m-k+1}},$ we have
$$\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} = 2 - \frac{m-k}{2^{m-k+1}} - \frac{3}{2^{m-k+1}} - \sum_{i=0}^{k-2} \binom{m-i}{k-i} \frac{1}{2^{m-i}}.$$
Therefore, 
$$\sum_{i = 1}^m \binom{i}{k}\frac{1}{2^i} \leq 2.$$
A: Another estimate for $\sum_{i=1}^m\frac1{\sqrt i}$ is 
$$2\sqrt{m-1}-2=\int_1^{m-1} x^{-1/2}\, dx  \le \sum_{i=1}^m\frac1{\sqrt i}\le1+ \int_1^m x^{-1/2}\, dx=2\sqrt m-1. $$
Thus we can remove the summands with $i<k$ by considering
$$ 4\sqrt m+2 -4\sqrt{k-2}$$
A: Not an aswer but some simple results that might help. Letting 
$$S_{m,k} = \sum_{i=k}^m {i \choose k} 2^{-i}$$
then
$$ \sum_{k=0}^m S_{m,k} =m$$
$$ |S_{m,k+1} - S_{m,k} | \le \frac{m}{k}S_{m,k}  $$
