A bound on a product

• Aug 23rd 2010, 09:06 AM
galois
A bound on a product
Hi there,

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

$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...
• Aug 24th 2010, 01:16 AM
red_dog
We have to prove the inequality

$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 $1\leq k\leq n$

We use the mathematical induction.

$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 $P(k)$ is true and we prove that $P(k+1)$ is also true.

$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:

$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)=$

$=\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\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$

$\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\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$

$\leq\displaystyle\frac{1}{2^{n-k}}(1+1)=\frac{1}{2^{n-k}}\cdot 2=\frac{1}{2^{n-k-1}}$
• Aug 24th 2010, 12:39 PM
Bruno J.
Quote:

Originally Posted by galois
Hi there,

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

$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 $i=0, \dots, k-1$, let $X_i$ denote a random variable which takes the value $0$ with probability $2^{i-n}$, and the value $1$ otherwise. Suppose moreover that these random variables are independent. Then $\prod_{i=0}^{k-1} (1- 2^{i-n})$ is the probability that all of the $X_i$ take the value $1$, hence $1-\prod_{i=0}^{k-1} (1- 2^{i-n})$ is the probability that not all of the $X_i$ take on the value $1$, i.e. that at least one of them take the value $0$. This is clearly less than $\sum_{i=0}^{k-1}P(X_i=0) = 2^{-n}(1+2^1+\dots+2^{k-1})<2^{k-n}$.