# Thread: A bound on a product

1. ## A bound on a product

Hi there,

Could anyone give me some tips on how to show for $\displaystyle k \le n$

$\displaystyle 1 - \prod_{i=0}^{k-1} (1- 2^{i-n}) \le 2^{k-n}$

I have no idea where to start. I expanded it out and you can see that the 1s cancel, but past that I am lost...

2. We have to prove the inequality

$\displaystyle P(k): \ 1-\displaystyle\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)\leq\frac{1}{2^{n-k}}$, for all integers k such as $\displaystyle 1\leq k\leq n$

We use the mathematical induction.

$\displaystyle P(1): \ 1-\displaystyle\left(1-\frac{1}{2^n}\right)\leq\frac{1}{2^{n-1}}\Leftrightarrow\frac{1}{2^n}\leq\frac{1}{2^{n-1}}$, which is true.

Suppose $\displaystyle P(k)$ is true and we prove that $\displaystyle P(k+1)$ is also true.

$\displaystyle P(k+1): \ 1-\displaystyle\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)\left(1-\frac{1}{2^{n-k}}\right)\leq\frac{1}{2^{n-k-1}}$

We have:

$\displaystyle 1-\displaystyle\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)\left(1-\frac{1}{2^{n-k}}\right)=$

$\displaystyle =\left[1-\displaystyle\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)\right]+$

$\displaystyle +\displaystyle\frac{1}{2^{n-k}}\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)\leq$

$\displaystyle \leq\displaystyle\frac{1}{2^{n-k}}+\frac{1}{2^{n-k}}\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)=$

$\displaystyle =\displaystyle\frac{1}{2^{n-k}}\left[1+\left(1-\frac{1}{2^n}\right)\left(1-\frac{1}{2^{n-1}}\right)\ldots\left(1-\frac{1}{2^{n-k+1}}\right)\right]\leq$

$\displaystyle \leq\displaystyle\frac{1}{2^{n-k}}(1+1)=\frac{1}{2^{n-k}}\cdot 2=\frac{1}{2^{n-k-1}}$

3. Originally Posted by galois
Hi there,

Could anyone give me some tips on how to show for $\displaystyle k \le n$

$\displaystyle 1 - \prod_{i=0}^{k-1} (1- 2^{i-n}) \le 2^{k-n}$

I have no idea where to start. I expanded it out and you can see that the 1s cancel, but past that I am lost...
Here's another idea. For each $\displaystyle i=0, \dots, k-1$, let $\displaystyle X_i$ denote a random variable which takes the value $\displaystyle 0$ with probability $\displaystyle 2^{i-n}$, and the value $\displaystyle 1$ otherwise. Suppose moreover that these random variables are independent. Then $\displaystyle \prod_{i=0}^{k-1} (1- 2^{i-n})$ is the probability that all of the $\displaystyle X_i$ take the value $\displaystyle 1$, hence $\displaystyle 1-\prod_{i=0}^{k-1} (1- 2^{i-n})$ is the probability that not all of the $\displaystyle X_i$ take on the value $\displaystyle 1$, i.e. that at least one of them take the value $\displaystyle 0$. This is clearly less than $\displaystyle \sum_{i=0}^{k-1}P(X_i=0) = 2^{-n}(1+2^1+\dots+2^{k-1})<2^{k-n}$.