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

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.

• 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 1 '14 at 17:10
• @Awesome You should make your comment an answer. – 6005 May 1 '14 at 18:51
• Or @SteveKass.${}$ – 6005 May 1 '14 at 18:52
• @SteveKass, you got some of the inequalities backwards. – Barry Cipra May 1 '14 at 19:01
• 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 2 '14 at 15:02

## 3 Answers

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

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

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

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.

• 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. – blue May 2 '14 at 4:12