Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By Vinod

Thread: Combinatorial inequality

  1. #1
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension
    Posts
    160
    Thanks
    15

    Combinatorial inequality

    I have to prove that if $\displaystyle n_{1}+n_{2}=n $ and$\displaystyle \frac{n_{1}}{n}=p$, then prove $\displaystyle \binom rk (p-\frac{k}{n})^k (q-\frac{r-k}{n})^{r-k}<\frac{\binom{r}{k}\binom{n-r}{n_{1}-k}}{\binom {n}{n_{1}}}<\binom rk p^k q^{r-k}(1-\frac{r}{n})^{-r}$
    I have tried and simplified it to show that this reduces to proving $\displaystyle (n_{1}-k)^k (n-n_{1}-r+k)^{r-k}<\frac{\binom{r}{k}\binom{n-r}{n_{1}-k}}{\binom {n}{n_{1}}}<{n_{1}}^k(n-n_{1})^{r-k}(n-r)^{-r}$

    But I cant see how to proceed further to prove this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    1,074
    Thanks
    317

    Re: Combinatorial inequality

    Quote Originally Posted by earthboy View Post
    I have to prove that if $\displaystyle n_{1}+n_{2}=n $ and$\displaystyle \frac{n_{1}}{n}=p$, then prove $\displaystyle \binom rk (p-\frac{k}{n})^k (q-\frac{r-k}{n})^{r-k}<\frac{\binom{r}{k}\binom{n-r}{n_{1}-k}}{\binom {n}{n_{1}}}<\binom rk p^k q^{r-k}(1-\frac{r}{n})^{-r}$
    I have tried and simplified it to show that this reduces to proving $\displaystyle (n_{1}-k)^k (n-n_{1}-r+k)^{r-k}<\frac{\binom{r}{k}\binom{n-r}{n_{1}-k}}{\binom {n}{n_{1}}}<{n_{1}}^k(n-n_{1})^{r-k}(n-r)^{-r}$

    But I cant see how to proceed further to prove this.
    Do we know that q = 1 - p ? And so q = n2/n ? where n2 = n sub 2

    Also, in your second inequality rCk should have been divided out from the middle expression as well as the left and right.
    Last edited by Debsta; Nov 12th 2018 at 03:46 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension
    Posts
    160
    Thanks
    15

    Re: Combinatorial inequality

    Quote Originally Posted by Debsta View Post
    Do we know that q = 1 - p ? And so q = n2/n ? where n2 = n sub 2

    Also, in your second inequality rCk should have been divided out from the middle expression as well as the left and right.
    Yes, we know that $\displaystyle q=1-p$ and so $\displaystyle q=n_{2}/n$.
    Thanks for the correction,$\displaystyle \binom rk$ should have been divided out in the middle.
    so we have to prove : $\displaystyle (n_{1}-k)^k (n-n_{1}-r+k)^{r-k}<\frac{\binom{n-r}{n_{1}-k}}{\binom {n}{n_{1}}}<{n_{1}}^k(n-n_{1})^{r-k}(n-r)^{-r}$
    Last edited by earthboy; Nov 12th 2018 at 04:20 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),Maharashtra,India
    Posts
    364
    Thanks
    6

    Re: Combinatorial inequality

    Quote Originally Posted by earthboy View Post
    Yes, we know that $\displaystyle q=1-p$ and so $\displaystyle q=n_{2}/n$.
    Thanks for the correction,$\displaystyle \binom rk$ should have been divided out in the middle.
    so we have to prove : $\displaystyle (n_{1}-k)^k (n-n_{1}-r+k)^{r-k}<\frac{\binom{n-r}{n_{1}-k}}{\binom {n}{n_{1}}}<{n_{1}}^k(n-n_{1})^{r-k}(n-r)^{-r}$
    Hello,
    You have to multiply the middle term $q^k$ by $n^k$ and $n^{r-k}$
    Thanks from earthboy
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),Maharashtra,India
    Posts
    364
    Thanks
    6

    Re: Combinatorial inequality

    Quote Originally Posted by Vinod View Post
    Hello,
    You have to multiply the middle term $q^k$ by $n^k$ and $n^{r-k}$
    Hello,you have to multiply last term by $n^r$
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Feb 2010
    From
    in the 4th dimension
    Posts
    160
    Thanks
    15

    Re: Combinatorial inequality

    Quote Originally Posted by Vinod View Post
    Hello,you have to multiply last term by $n^r$
    can you clarify a bit. I tried doing the manipulations but I am getting stuck in the middle, for both inequalities.
    Last edited by earthboy; Nov 17th 2018 at 01:02 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),Maharashtra,India
    Posts
    364
    Thanks
    6

    Re: Combinatorial inequality

    Quote Originally Posted by earthboy View Post
    can you clarify a bit. I tried doing the manipulations but I am getting stuck in the middle, for both inequalities.
    Hello,

    This is a limit theorem for the hypergeometric distribution. If n is large and $\frac{n_1}{n}=p$, then the probability $q_k$ is close to, more precisely,

    $\binom{r}{k}(p-\frac{k}{n})(q-\frac{r-k}{n})^{r-k}\leq q_k\leq \binom{r}{k} p^k q^{r-k}(1-\frac{r}{n})^{-r}$ where

    $q_k=\frac{\binom{r}{k}(\binom{n-r}{r-k}}{\binom{n}{r}}$

    $q_k$ is most probably close to $\binom{r}{k}p^k q^{r-k}$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binomial Inequality - Combinatorial Proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 24th 2011, 03:34 PM
  2. combinatorial inequality
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Aug 26th 2010, 03:03 PM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jun 4th 2010, 05:12 PM
  4. combinatorial sum
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2009, 11:46 AM
  5. Combinatorial argument
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 17th 2009, 03:46 PM

/mathhelpforum @mathhelpforum