Compute $\sum_{k=0}^{n}{\frac{\binom{n}{k}}{k+1}}$ Compute the sum:
$$\sum_{k=0}^{n}{\frac{\binom{n}{k}}{k+1}}$$
I tried to solve it:
$$\sum_{k=0}^{n}{\frac{(k+1)(k+2)\binom{n+2}{k+2}}{(n+1)(n+2)(k+2)}}=\sum_{k=0}^{n}{\frac{(k+1)\binom{n+2}{k+2}}{(n+1)(n+2)}}=\frac{1}{(n+1)(n+2)}\sum_{k=0}^{n}(k+1)\binom{n+2}{k+2}$$
But from this point I'm stuck.
Thank you!

You should start by showing that:
$$ \frac{n\choose k}{k+1} = \frac{1}{n+1} {n+1\choose k+1} $$
Then notice you're summing over $k$, so you're free to take this $\frac{1}{n+1}$ out of the sum as a constant factor:
$$ \sum_{k=0}^n \frac{n\choose k}{k+1} = \frac{1}{n+1}\sum_{k=0}^n  {n+1\choose k+1} $$
Finally,
$$ \sum_{k=0}^n  {n+1\choose k+1} = \left[\sum_{k=0}^{n+1}  {n+1\choose k+1}\right] - {n+1\choose n+1}$$
and you should be able to evaluate these two terms, by standard results about binomial coefficients.

 1. The first term is the sum over row $(n+1)$ of Pascal's triangle, which gives $2^{n+1}$.


 2. The second term is just $1$.


 So the final answer is: $$ \sum_{k=0}^n \frac{n\choose k}{k+1} = \frac{2^{n+1} - 1}{n+1} $$

