Results 1 to 3 of 3

Thread: A bound on a product

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    3

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor red_dog's Avatar
    Joined
    Jun 2007
    From
    Medgidia, Romania
    Posts
    1,252
    Thanks
    5
    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}}$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by galois View Post
    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}$.
    Last edited by Bruno J.; Aug 24th 2010 at 12:50 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. upper bound for a product
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Feb 9th 2011, 04:32 AM
  2. Replies: 0
    Last Post: Feb 19th 2010, 01:06 AM
  3. greatest least bound and least upper bound proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 4th 2009, 04:44 PM
  4. Upper bound/Lower bound?
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: Sep 13th 2009, 10:48 AM
  5. least upper bound and greatest lower bound
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Sep 22nd 2007, 09:59 AM

Search Tags


/mathhelpforum @mathhelpforum