A bound on a product

**galois** · August 23rd 2010, 09:06 AM

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...

**red_dog** · August 24th 2010, 01:16 AM

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

**Bruno J.** · August 24th 2010, 12:39 PM

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}$ .

Thread: A bound on a product

LinkBack

Thread Tools

Display

A bound on a product

Similar Math Help Forum Discussions

upper bound for a product

Partial sets/ Least upper bound/Greastest lower bound/Lattices

greatest least bound and least upper bound proof

Upper bound/Lower bound?

least upper bound and greatest lower bound

Search Tags