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!
 A: One approach is to determine $f(1)$ for
$$f(x) = \sum_{k=0}^n\binom n k \frac{x^{k+1}}{k+1}$$
Notice that by taking the derivative, the $k+1$ denominators will go away:
$$f'(x) = \sum_{k=0}^n\binom n k {x^k} = (1+x)^n$$
Then use $$f(1)-f(0) = \int_0^1 f'(x)dx = \left[\frac{(1+x)^{n+1}}{n+1}\right]^{x=1}_{x=0}$$
because $f(0)$ and the integral are easy to compute.

As an aside, and as you asked in a comment, this approach generalizes nicely to sums of the form
$$s_{n,m} = \sum_{k=0}^n \frac1{k+m} \binom n k $$
for integers $m\geqslant 1$: The bottom line is then
$$f(1)-\underbrace{f(0)}_{=0} = \left[\frac{(1+x)^{n+m}}{n+m}\right]^{x=1}_{x=0} = \frac{2^{n+m}-1}{n+m}$$
A: 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} $$

