Binomial Theorem Sum

Question

How would I find the sum below?

$$ \sum_{k=0}^{n} {\frac{1}{k+1} {n \choose k}}=?$$

I need help starting on the problem. Would I first need to utilize the Binomial Theorem proof to get started on it?

Thank you.

Answer 1

We know that for any value of $x$:

(1) $$(1+x)^n=\sum_{k=0}^n\binom nk x^k$$

If we integrate both sides we get that:

(2) $$\frac{(1+x)^{n+1}}{n+1} + C = \sum_{k=0}^n\binom nk\frac{x^{k+1}}{k+1}$$

where $C$ is some constant.

Now to find the constant $C$ we put e.g. $x=0$ into (2).

So we get:

$$\frac{1}{n+1} + C = 0$$
$$C = -\frac{1}{n+1}$$

Now we put the found value of $C$ back into (2) and we get:

(3) $$ \frac{(1+x)^{n+1}}{n+1} - \frac{1}{n+1} = \sum_{k=0}^n\binom nk\frac{x^{k+1}}{k+1}$$

Finally we put $x=1$ into (3) and we get the answer we were looking for:

(4) $$ \frac{2^{n+1}-1}{n+1} = \sum_{k=0}^n\binom nk\frac{1}{k+1}$$

Answer 2

HINT: Start by proving that

$$(n+1)\binom{n}k=(k+1)\binom{n+1}{k+1}\;;$$

this can be done quite easily either algebraically or combinatorially. Then rewrite this identity in a way that lets you simplify $\frac1{k+1}\binom{n}k$ usefully. You don’t really need the binomial theorem at all.