More Combinatorial Fun: Evaluating Sums

[MarkFL]

Evaluate the given sum:

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

 

[caffeinemachine]

Evaluate the given sum:

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

Spoiler

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]

Spoiler

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. :D

 

[caffeinemachine]

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. :D

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]

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:

Spoiler

$$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. (Sun)

 

[caffeinemachine]

You should get:

Spoiler

$$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. (Sun)

haha. I wasn't doing the algebra right. How silly of me.

 

[kaliprasad]

Should use MarkFL’s solution approach ( he had solved a problem in this approach)

Spoiler

(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]

Here's my solution:

Spoiler

Using the binomial theorem, we may state:

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

Next, apply the identities:

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

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

and so we have:

$$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:

$$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 $$S_n=\sum_{k=0}^n\left(\frac{1}{k+1}{n \choose k} \right)$$ we find:

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