Recursive sequence of binomial random variables Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$. 
I would like a left tail bound. Perhaps, for some $a>0$ and $0 < \epsilon < p$,
$$\mathbf P[X_k < (1+ p - \epsilon)^k ] \leq e^{-a k}.$$
 A: I claim is that $X_k$ stochastically dominates the following process, $W_k$. To make things a bit simpler, assume $X_1 = 2 = W_1$. (This is harmless, since we can just wait some geometric time until $X_{k}=2$ then start the process.)  Let $$q = \inf_{k \geq 2} \{\mathbf{P}[\text{Bin}(k,p) > pk]\}.$$ Since this converges as $k \to \infty$ (by normal approximation) we know that $q>0$. Now, define $W_1 = 2$ and 
$$W_{k+1} = W_k + (1/2)W_k \text{Ber(q)}.$$
Essentially the $W_k$ increase whenever $X_k$ increases by at least $X_k/2$ and otherwise does not change. One could then write a formal coupling, so that $W_k \preceq X_k$. The $W_k$ are much simpler to analyze. Each successful Ber($q$) trial results in an increase by a factor of $(1+p)$. So we can write
$$W_k = 2*(1+p)^{ \text{Bin}{(k,q)}}.$$
Let $q_k = \mathbf P[ \text{Bin}(k,q) \leq kq/2]$. By Chernoff, $q_k \leq e^{-a k}$ for some $a>0$. It follows that 
$$\mathbf P [ W_k \leq ( (1+p)^{q/2})^k]\leq q_k \leq e^{-a k}. $$
As $W_k \preceq X_k$ we take $\epsilon = (1+p)^{q/2} -1$ and have
$$\mathbf P[X_k \leq (1 + \epsilon)^k ] \leq e^{-ak}.$$
