Welcome to our community

Be a part of something great, join today!

More combinatorial fun!

  • Thread starter
  • Admin
  • #1

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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
Mar 10, 2012
834
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}$.
 
  • Thread starter
  • Admin
  • #3

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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. :eek:

And what was your solution. I'd be interested in a pre-calculus solution.
 
  • Thread starter
  • Admin
  • #5

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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. :eek:

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

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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. (Sun)
haha. I wasn't doing the algebra right. How silly of me.
 

kaliprasad

Well-known member
Mar 31, 2013
1,322
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)
 
  • Thread starter
  • Admin
  • #8

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
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}\)