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. 
Original:  How prove this inequality $\sum_{k=1}^{n}\frac{2k-1}{k\binom{n}{k}}\ge \frac{n}{2^{n-1}}$
 A: 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}$$
A: 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.
A: 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}$"
