I am reading a paper called "Fountain codes". For the random linear fountain codes, the success of decoding depends on whether the rank of the $(K+E) \times K$ random binary matrix (i.e., each element of this matrix is drawn uniformly from $0$ or $1$) is $K$. Note that $K \ge 1$, and $E \ge 0$.
We know the probability of the rank for the matrix to be $K$ (i.e., all column vectors of the matrix are linearly independent) is $(1-2^{-K-E})(1-2^{-(K-1)-E})\cdots(1-2^{-2-E})(1-2^{-1-E})$, which is stated to be greater than $1-2^{-E}$ without deduction. Thus, I try to prove $$ (1-2^{-K-E})(1-2^{-(K-1)-E})\cdots(1-2^{-2-E})(1-2^{-1-E})\geq 1-2^{-E}. $$
I tried with the following: \begin{align} & (1-2^{-K-E})(1-2^{-(K-1)-E})\cdots(1-2^{-2-E})(1-2^{-1-E})\\ = & \exp \left\{ \ln(1-2^{-K-E})+ \ln(1-2^{-(K-1)-E})+\cdots + \ln(1-2^{-2-E})+ \ln(1-2^{-1-E})\right\}\\ \mathop{\geq}^{\text{(a)}} & \exp\left\{ -\frac{2^{-K-E}}{1-2^{-K-E}} -\frac{2^{-(K-1)-E}}{1-2^{-(K-1)-E}} -\cdots -\frac{2^{-2-E}}{1-2^{-2-E}} -\frac{2^{-1-E}}{1-2^{-1-E}} \right\}, \end{align} which is not sufficient to obtain the result. Note that (a) follows from $\ln(1-x) \ge -\frac{x}{1-x}$ for $0< x < 1$.
I also tried with Mathematica as follows:
Assuming[Element[k, Integers] && k >= 1 && Element[e, Integers] &&
e >= 0, Reduce[Product[1 - 2^-(j + e), {j, 1, k}] >= 1 - 2^-e, e,
Integers]]
But it outputed:
Reduce::nsmet: This system cannot be solved with the methods available to Reduce. >>
Reduce[(2^e QPochhammer[2^-e, 1/2, 1 + k])/(-1 + 2^e) >=
1 - 2^-e, e, Integers]
Maybe some knowledge about $q$-Pochhammer symbol is needed. Thanks in advance!
Hint: use $$(1+x_{1})(1+x_{2})\cdots (1+x_{n})\ge 1+x_{1}+x_{2}+\cdots+x_{n}$$
so $$(1-2^{-K-E})(1-2^{-(K-1)-E})\cdots(1-2^{-2-E})(1-2^{-1-E})\ge 1-\left(2^{-1-E}+2^{-2-E}+\cdots+2^{-K-E}\right)=1-\sum_{k=1}^{\infty}\dfrac{1}{2^{k+E}}=1-2^{-E}$$