# More combinatorial fun!

#### MarkFL

Staff member
Evaluate the given sum:

$$\displaystyle S_n=\sum_{k=0}^n\left(\frac{1}{k+1}{n \choose k} \right)$$

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Evaluate the given sum:

$$\displaystyle S_n=\sum_{k=0}^n\left(\frac{1}{k+1}{n \choose k} \right)$$
The integral of the binomial expansion of $(1+x)^n$ from $x=0$ to $1$ is the required sum. Thus $\int_{0}^1(1+x)^ndx=S_n$. This gives $S_n=\left.\frac{(x+1)^{n+1}}{n+1}\right|_{0}^1= \frac{2}{n} -\frac{1}{n}$.

#### MarkFL

Staff member
The integral of the binomial expansion of $(1+x)^n$ from $x=0$ to $1$ is the required sum. Thus $\int_{0}^1(1+x)^ndx=S_n$. This gives $S_n=\left.\frac{(x+1)^{n+1}}{n+1}\right|_{0}^1= \frac{2}{n} -\frac{1}{n}$.
While this is an very straightforward method (much more elegant than my pre-calculus approach), your end result is incorrect, but only because you did not apply the FTOC correctly. #### caffeinemachine

##### Well-known member
MHB Math Scholar
While this is an very straightforward method (much more elegant than my pre-calculus approach), your end result is incorrect, but only because you did not apply the FTOC correctly. Ah.. I see. I should get $\frac{2}{n+1} - \frac{1}{n+1} = \frac{1}{n+1}$. Where have I committed a mistake? I cannot find it. And what was your solution. I'd be interested in a pre-calculus solution.

#### MarkFL

Staff member
Ah.. I see. I should get $\frac{2}{n+1} - \frac{1}{n+1} = \frac{1}{n+1}$. Where have I committed a mistake? I cannot find it. And what was your solution. I'd be interested in a pre-calculus solution.
You should get:

$$\displaystyle S_n=\left.\frac{(x+1)^{n+1}}{n+1}\right|_{0}^1= \frac{(1+1)^{n+1}}{n+1}-\frac{(0+1)^{n+1}}{n+1}=\frac{2^{n+1}-1}{n+1}$$

I will post my solution soon, but I want to give others a chance to post their solutions first. #### caffeinemachine

##### Well-known member
MHB Math Scholar
You should get:

$$\displaystyle S_n=\left.\frac{(x+1)^{n+1}}{n+1}\right|_{0}^1= \frac{(1+1)^{n+1}}{n+1}-\frac{(0+1)^{n+1}}{n+1}=\frac{2^{n+1}-1}{n+1}$$

I will post my solution soon, but I want to give others a chance to post their solutions first. haha. I wasn't doing the algebra right. How silly of me.

##### Well-known member
Should use MarkFL’s solution approach ( he had solved a problem in this approach)

(nCk)/(k+1) = n!/(k! * (n-k)!) * (k+1) = 1/(n+1) ( n+ 1 C k+1)

So sum (nCk)/(k+1) = 1/(n+1) (sum (n+1 C k) - (n+1 C 0))
= 1/(n+1) (sum (n+1Ck) - 1)
= 1/(n+1) ( 2^(n+1) – 1)

#### MarkFL

Staff member
Here's my solution:

Using the binomial theorem, we may state:

$$\displaystyle 2^{n+1}=(1+1)^{n+1}=\sum_{k=0}^{n+1}{n+1 \choose k}$$

Next, apply the identities:

$$\displaystyle {n \choose 0}=1$$

$$\displaystyle {n+1 \choose r}=\frac{n+1}{r}{n \choose r-1}$$

and so we have:

$$\displaystyle 2^{n+1}=1+(n+1)\sum_{k=1}^{n+1}\left(\frac{1}{k}{n \choose k-1} \right)$$

Subtracting through by $1$ and re-indexing the sum, we have:

$$\displaystyle 2^{n+1}-1=(n+1)\sum_{k=0}^{n}\left(\frac{1}{k+1}{n \choose k} \right)$$

Dividing through by $n+1$ and using $$\displaystyle S_n=\sum_{k=0}^n\left(\frac{1}{k+1}{n \choose k} \right)$$ we find:

$$\displaystyle S_n=\frac{2^{n+1}-1}{n+1}$$