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?

I'm pretty sure there is no closed form for this sum and it is far from simple.  This sum looks like one involved in finding the expected value of the length of the longest run of successes of a bernoulli random variable.  See for instance this question, unfortunately the it's pretty opaque and it's been a while since I was trying to do that sum.
Here's a way of converting the problem to a derivative problem, although I don't know how useful it will be.  Recall $\binom{k+i}{i}=\binom{k+i}{k}=[x^k y^i](x+y)^{k+i}$, where $[m](p)$ denotes the coefficient on the term $m$ in the polynomial/series $p$.  So now we want to find
$$\sum_{i=0}^m 2^i[x^k y^i](x+y)^{k+i}.$$
Notice if we take the $k$th derivative of $(x+y)^{k+i}$ with respect to $x$ at $x=0$ and $y=1$, we get the coefficient we want times $k!$.  Thus we can write the sum as
$$\sum_{i=0}^m\frac{2^i}{k!}\frac{d^k}{dx^k}(x+1)^{k+i}|_{x=0}$$
Now a lot of this stuff can be pulled out of the sum, giving us
$$\frac{1}{k!}\frac{d^k}{dx^k}\left((x+1)^k\sum_{i=0}^m 2^i(x+1)^i\right)|_{x=0}$$
The inside is now a geometric series so we can find its sum
$$\frac{1}{k!}\frac{d^k}{dx^k}\left((x+1)^k\frac{(2(x+1))^{m+1}-1}{2(x+1)-1}\right)|_{x=0}$$
$$\frac{1}{k!}\frac{d^k}{dx^k}\left(\frac{2^{m+1}(x+1)^{m+k+1}-(x+1)^k}{2x-1}\right)|_{x=0}$$
It may be possible to find an explicit form for this derivative or at least a recurrence relation, although I couldn't.
However, if $k$ is fixed you can find a closed form: the binomial coefficient $\binom{k+i}{k}$ is a degree $k$ polynomial, and $\sum_n b^n P(n)$ can be computed for any base $b$ and polynomial $P$ using a trick.  Take $\frac{d^k}{db^k}\sum_n b^n$ for $k$ ranging from 1 to the degree of $P$.  The derivatives of the summands form a basis for polynomials of degree $k$, and the derivatives of the corresponding sums let us calculate the sum for $b^n$ times any polynomial.
As far as an upper bound, a VERY rough one can be gotten from the approximation $\binom{mn}{n}\approx\frac{m^{m(n-1)+1}}{(m-1)^{(m-1)(n-1)}\sqrt{n}}$.  Because $i\le m\le Ck$, we can rewrite the sum as $$\sum_{i=0}^m\frac{2^i(C+1)^{Ck-C+k}}{C^{Ck-C}\sqrt{k}}=\frac{(2^{m+1}-1)(C+1)^{Ck-C+k}}{C^{Ck-C}\sqrt{k}}.$$
Notice this is equivalent to using the upper bound from the other answer and then applying the approximation I mentioned, so this will also be over by a factor of about 2.  Depending on what you need (ie if you just want big O), a factor of 2 may not matter to you.
