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

Answer 1

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

Answer 2

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.

Answer 3

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