2
$\begingroup$

I am learning probabilistic method and try to practice with Combinatorics examples. Recently I read this question and wonder how to show

$$\sum_{k=1}^n \binom{n}{k}^{-1} > \frac{n}{2^n}$$

How to get reciprocal of binomial coefficient. This is the probability of choosing particular $k$ element subset of ${1,2,\cdots, n}$. However why do we sum over all subsets?

Perhaps also $ \frac{n}{2^n}$ is the odds of a random subset of any size having exactly one element?


Maybe try another starting point than this.
I missed a good point in the comments - which is good enough to answer my question. The same post also had

$$\sum_{k=1}^n \binom{n}{k}^{-1} > \frac{n^2}{2^n}$$

Now with a square.

Original: How prove this inequality $\sum_{k=1}^{n}\frac{2k-1}{k\binom{n}{k}}\ge \frac{n}{2^{n-1}}$

$\endgroup$
  • 1
    $\begingroup$ Choosing a subset from k element subset set has better probability than choosing a subset from a set all possible sets. This goes for all k. add them $\endgroup$ – evil999man May 1 '14 at 17:10
  • $\begingroup$ @Awesome You should make your comment an answer. $\endgroup$ – 6005 May 1 '14 at 18:51
  • $\begingroup$ Or @SteveKass.${}$ $\endgroup$ – 6005 May 1 '14 at 18:52
  • $\begingroup$ @SteveKass, you got some of the inequalities backwards. $\endgroup$ – Barry Cipra May 1 '14 at 19:01
  • $\begingroup$ Thanks, Barry! Since I can't edit the comment, I'll delete it and try again. Here's a corrected version: $\binom{n}{k}<2^n$, so $\binom{n}{k}^{-1}>\frac{1}{2^n}$. If you add up $n$ things, each of which is greater than $\frac{1}{2^n}$, your result must be more than $n$ times $\frac{1}{2^n}$. $\endgroup$ – Steve Kass May 2 '14 at 15:02
0
$\begingroup$

To prove: $$\frac{1}{\binom{n}{1}}+\frac{1}{\binom{n}{2}}+\dots +\frac{1}{\binom{n}{n}}>\frac{n}{2^n}$$ LHS counts the probability of choosing a number say $k$ from $\{1,2,\dots ,n\}$ and then picking a subset of size $k$. Choosing different $k$'s correspond to mutually exclusive events. Hence the probabilities are added.

RHS: pick a number say $k$ among $\{1,2,\dots ,n\}$ in $n$ ways. Irrespective of $k$, the probability of choosing a subset of size $k$ among the subsets of size $k$ is greater than the probability choosing a subset of size $k$ among the subsets of $\{1,2,\dots ,n\}$ ie., $\frac{1}{\binom{n}{k}}>\frac{1}{2^n}$

PS: We can improve the inequality by replacing "$2^n$" by "$\binom{n}{\lfloor \frac{n}{2} \rfloor}$"

$\endgroup$
1
$\begingroup$

lemma: $$\dfrac{2}{1}+\dfrac{2^2}{2}+\cdots+\dfrac{2^n}{n}=\dfrac{2^n}{n}\sum_{k=0}^{n-1} \dfrac{1}{\binom{n-1}{k}}$$ Proof:can see link from the lemma: we have

$$\sum_{k=1}^{n}\dfrac{1}{\binom{n}{k}}=\dfrac{n+1}{2^{n+1}}\left(2+\dfrac{2^2}{2}+\cdots+\dfrac{2^n}{n}\right)>\dfrac{n+1}{2^n}>\dfrac{n}{2^n}$$

and since $$2^k>k^2,k\ge 2$$ so $$\dfrac{n+1}{2^{n+1}}\left(2+\dfrac{2^2}{2}+\cdots+\dfrac{2^{n}}{n}\right)>\dfrac{n^2}{2^n}$$

$\endgroup$
  • $\begingroup$ Is that equality ? The link is United States TST 2000 $\endgroup$ – cactus314 May 2 '14 at 12:38
  • $\begingroup$ Assuming this IMO problem and $\boxed{2^k > k^2}$ we can (im)prove the bound, yes :-) $\endgroup$ – cactus314 May 2 '14 at 13:18
0
$\begingroup$

Choosing a subset from a set of $k$ element subsets has greater probability than choosing one from a set of all subsets. This goes for all $k$. Add them.

$\endgroup$
  • $\begingroup$ Do you mean "for every $k$, the probability of choosing a subset of $\{1,\cdots,n\}$ that happens to have $k$ elements is greater than choosing a single given subset"? The current language seems very contorted - I was only able to figure out how to interpret it from the math, not the words. $\endgroup$ – blue May 2 '14 at 4:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.