Any good upper bounds for $\sum_{i = 0}^{m} 2^i {k+i \choose i}$? I am trying to solve a recursion (I faced it when I wanted to analyze the running time of an algorithm precisely). I reduced it to compute a "good" upper bound for $\sum_{i = 0}^{m}2^i {k + i \choose i}$. We have these assumptions that $1 < m \leq Ck$, for some $C\in \mathbb{N}$.
I have tried many approximations but the bounds are not what I want. They are very loose. On the other hand, it doesn't look like a very sophisticated summation but I have so much difficulty solving it!
Does anyone have any ideas?

First step is that  we can actually give to the sum a closed expression in terms of the Hypergeometric function
In fact can rewrite the sum as follows (allow me to change a bit your notation)
$$
\eqalign{
  & S(n,m,x) = \sum\limits_{i = 0}^m {\left( \matrix{ n + i \cr i \cr}  \right)x^{\,\,i} }
  = \sum\limits_{i = 0}^m {\left( { - 1} \right)^{\,\,i} \left( \matrix{ - n - 1 \cr i \cr}  \right)x^{\,\,i} }  = \quad \quad (1)  \cr 
  &  = \sum\limits_{0\, \le \,i\, \le \,m} {\left( \matrix{ - n - 1 \cr i \cr}  \right)\left( { - x} \right)^{\,\,i} }
  = \left( { - x} \right)^{\,\,m} \sum\limits_{0\, \le \,k\,\left( { \le \,m} \right)}
 {\left( \matrix{ - n - 1 \cr  m - k \cr}  \right)\left( { - x} \right)^{\, - k} }  = \quad \quad (2)  \cr 
  &  = x^{\,\,m} \sum\limits_{0\, \le \,k\,\left( { \le \,m} \right)}
 {\left( \matrix{n + m - k \cr m - k \cr}  \right)x^{\, - k} }
  = x^{\,\,m} \sum\limits_{0\, \le \,k\, \le \,m}
 {{{\left( {n + m - k} \right)!} \over {n!\left( {m - k} \right)!}}x^{\, - k} }  = \quad \quad (3)  \cr 
  &  = x^{\,\,m} {{\left( {n + m} \right)!} \over {m!n!}}\sum\limits_{0\, \le \,k\, \le \,m}
 {{{\left( {n + m - k} \right)!m!} \over {\left( {n + m} \right)!\left( {m - k} \right)!}}x^{\, - k} }  = \quad \quad (4)  \cr 
  &  = x^{\,\,m} \left( \matrix{ n + m \cr m \cr}  \right)\sum\limits_{0\, \le \,k\,\left( { \le \,m} \right)}
 {{{\left( \matrix{m \cr k \cr}  \right)} \over {\left( \matrix{n + m \cr k \cr}  \right)}}x^{\, - k} }  = \quad \quad (5)  \cr 
  &  = x^{\,\,m} \left( \matrix{n + m \cr  m \cr}  \right)\sum\limits_{0\, \le \,k\,\left( { \le \,m} \right)}
 {{{m^{\,\underline {\,k\,} } } \over {\left( {n + m} \right)^{\,\underline {\,k\,} } }}x^{\, - k} }  = \quad \quad (6)  \cr 
  &  = x^{\,\,m} \left( \matrix{n + m \cr m \cr}  \right)\sum\limits_{0\, \le \,k\,\left( { \le \,m} \right)}
 {{{\left( { - m} \right)^{\,\overline {\,k\,} } }
 \over {\left( { - n - m} \right)^{\,\overline {\,k\,} } }}x^{\, - k} }  = \quad \quad (7)  \cr 
  &  = x^{\,\,m} \left( \matrix{  n + m \cr m \cr}  \right)
 {}_2F_{\,1} \left( {\left. {\matrix{ {1,\; - m}  \cr { - \left( {n + m} \right)}  \cr } \;} \right|\;{1 \over x}} \right)
 \quad \quad (8) \cr} 
$$
where $a^{\,\underline {\,k\,} } ,\quad a^{\,\overline {\,k\,} } $ represent respectively the Falling and Rising Factorial
and the various steps are:
-1) upper negation;

*

*


*invert the summation index;



*


*binomial expressed as factorials;



*


*extraction of the leading binomial component;



*


*, 6), 7) rewriting of the binomial fraction



*


*conversion to Hypergeometric.
Note the upper bound of the sum being indicated in brackets when it is implicit in the binomial or falling factorial.



For what concerns the establishing of an upper bound, it seems that you are referring
to the case in which $n << m$.
If it is so, we can use one of the expression above, eg. the (6). The coefficient in the sum can be rewritten in various ways
$$
\eqalign{
  & {{m^{\,\underline {\,k\,} } } \over {\left( {m + n} \right)^{\,\underline {\,k\,} } }}\,
 = {{\left( {m + n - k} \right)^{\,\underline {\,n\,} } } \over {\left( {m + n} \right)^{\,\underline {\,n\,} } }}
 = {{\left( {m + 1 - k} \right)^{\,\overline {\,n\,} } } \over {\left( {m + 1} \right)^{\,\overline {\,n\,} } }} =   \cr 
  &  = {{\Gamma \left( {m + 1 + n - k} \right)\Gamma \left( {m + 1} \right)}
 \over {\Gamma \left( {m + 1 - k} \right)\Gamma \left( {m + 1 + n} \right)}} =   \cr 
  &  = \prod\limits_{j = 0}^{n - 1} {{{m + 1 + j - k} \over {m + 1 + j}}}
  = \prod\limits_{j = 0}^{n - 1} {\left( {1 - {k \over {m + 1 + j}}} \right)}  \cr} 
$$
and from these we can proceed with various approximations, depending on the required acurracy.
For instance
$$
{{m^{\,\underline {\,k\,} } } \over {\left( {m + n} \right)^{\,\underline {\,k\,} } }}
 = \prod\limits_{j = 0}^{n - 1} {\left( {1 - {k \over {m + 1 + j}}} \right)}
  < \mathop  \approx \limits_{n <  < m} \left( {1 - {k \over {m + \left( {n + 1} \right)/2}}} \right)^n 
$$
and then proceeding to take the log and simplify (with the accuracy needed), e.g.
$$
 \approx \exp \left( { - {{nk} \over {m + \left( {n + 1} \right)/2}}} \right)
$$
which is suitable to be summed in $k$.
Or you can start from the expression through the Gamma function and apply the Stirling approximation, ...
