Derivation formula for sum including newton symbol

Question

So i was asked to derive formula for given sum:

$$ {n\choose0} +\frac 12 {n\choose1}+\frac 13{n\choose2}+...+\frac 1{n+1}{n\choose n} $$

So i made few attempts, but not for all steps i'm sure that are correct.

1. $S=\sum_{k=0}^n \frac1{k+1}{n\choose k} $

2. $ S(n+1)= \sum_{k=0}^n \frac{n+1}{k+1}{n\choose k}= \sum_{k=0}^n {n+1\choose k+1} \quad $

3. $S(n+1)=2^{n+1}-1 $
4. So $S =\frac{2^{n+1}-1}{n+1} $

Thanks in advance

Answer 1

Your proof is both elegant and correct! Here's another way: $$ \sum_{k=0}^n\frac 1 {k + 1}{n \choose k} = \sum_{k=0}^n{n \choose k}\int_0^1x^kdx=\int_0^1(1+x)^ndx=\frac{2^{n+1}-1}{n+1} $$

Answer 2

Just a small variation of OP's approach.

We obtain \begin{align*} \color{blue}{\sum_{j=0}^n\frac{1}{j+1}\binom{n}{j}}&=\frac{1}{n+1}\sum_{j=0}^n\binom{n+1}{j+1}\tag{1}\\ &=\frac{1}{n+1}\sum_{j=1}^{n+1}\binom{n+1}{j}\tag{2}\\ &\,\,\color{blue}{=\frac{1}{n+1}\left(2^{n+1}-1\right)}\tag{3} \end{align*}

Comment:

• In (1) we use the binomial identity $\binom{p+1}{q+1}=\frac{p+1}{q+1}\binom{p}{q}$.

• In (2) we shift the index and start with $j=1$.

• In (3) we apply the binomial theorem.