Probabilistic proof that $\sum \binom{n}{k}^{-1} > \frac{n}{2^n}$

Question

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

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 — evil999man, May 01 '14 at 17:10
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}$. — Steve Kass, May 02 '14 at 15:02

math110 · Answer 1 · 2014-05-02T13:14:45.473

1

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

edited May 02 '14 at 13:14

answered May 02 '14 at 04:17

math110

93,304

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

evil999man · Answer 2 · 2014-05-02T03:33:00.553

0

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.

edited May 02 '14 at 03:33

answered May 01 '14 at 16:59

evil999man

6,018

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. – anon May 02 '14 at 04:12

score 0 · Accepted Answer · answered May 02 '14 at 12:34

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

Probabilistic proof that $\sum \binom{n}{k}^{-1} > \frac{n}{2^n}$

3 Answers3