Results 1 to 3 of 3

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

    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}}
    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 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}.
    Last edited by Bruno J.; August 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: February 9th 2011, 04:32 AM
  2. Replies: 0
    Last Post: February 19th 2010, 01:06 AM
  3. greatest least bound and least upper bound proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 4th 2009, 04:44 PM
  4. Upper bound/Lower bound?
    Posted in the Pre-Calculus Forum
    Replies: 7
    Last Post: September 13th 2009, 10:48 AM
  5. least upper bound and greatest lower bound
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 22nd 2007, 09:59 AM

Search Tags


/mathhelpforum @mathhelpforum