A recurrence relation of $$S_n =\sum_{k=0}^{n} \frac{1}{\binom{n}{k}}$$ is

$$ \frac{n+2}{\binom{n}{k}} - \frac{2n+2}{\binom{n+1}{k}} = \frac{n-k}{\binom{n}{k+1}} - \frac{n+1-k}{\binom{n}{k}}, \quad 0 \leq k < n. $$

Summing from $k=0$ to $n-1$, we have $$ \begin{aligned} &\sum_{k=0}^{n-1} \left[ \frac{n+2}{\binom{n}{k}} - \frac{2n+2}{\binom{n+1}{k}} \right] = \sum_{k=0}^{n-1} \left[ \frac{n-k}{\binom{n}{k+1}} - \frac{n+1-k}{\binom{n}{k}} \right] \\ \implies&(n+2)(S_n-1)-(2n+2)\left(S_{n+1}-1-\frac{1}{n+1}\right) = -n \\ \implies&(2n+2)S_{n+1} = (n+2)S_n+2n+2. \end{aligned} $$


$$ S_n = \sum_{k=0}^{n}\frac{1}{\binom{n}{k}} = \frac{n+1}{2^{n+1}}\sum_{k=0}^{n}\frac{2^{k+1}}{k+1}.$$

However, I wonder if there is a way to prove this in a combinatorial fashion?


Your Answer

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

Browse other questions tagged or ask your own question.