A problem I'm trying to figure out asks that I use the binomial theorem (or any other method I want) to evaluate $\sum_{k=0}^n \frac{1}{k+1} {n \choose k}$ in closed form.
The binomial theorem stated in my textbook: $(1+x)^n = {n\choose 0}+{n\choose 1}x+{n\choose 2}x^2+…+{n\choose k}x^k+…+{n\choose n}x^n$
I think the idea behind evaluating the summation to closed form is to perform some manipulation on the binomial theorem until it basically looks like what I want. My textbook only gives simplistic examples, like showing that $ \sum_{k=0}^n {n \choose k}$ by setting $x=1$. This doesn't really give me a good sense of how to do this problem.
Could I please have a hint?
Best Answer
Lucian's comment is perfectly fine. As an alternative, a nice old trick: $$\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\binom{n+1}{k+1}$$ hence: $$\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\sum_{k=1}^{n+1}\binom{n+1}{k}=\frac{2^{n+1}-1}{n+1}.$$