MHB More Combinatorial Fun: Evaluating Sums

  • Thread starter Thread starter MarkFL
  • Start date Start date
  • Tags Tags
    Fun
AI Thread Summary
The discussion focuses on evaluating the sum S_n = ∑(1/(k+1) * C(n, k)) from k=0 to n. Participants note an error in applying the Fundamental Theorem of Calculus (FTOC) in the initial solution attempt. A corrected approach leads to the result of 1/(n+1). There is interest in sharing pre-calculus solutions, with one participant expressing a desire to post their solution after others contribute. The conversation highlights the importance of correct algebraic manipulation in combinatorial problems.
MarkFL
Gold Member
MHB
Messages
13,284
Reaction score
12
Evaluate the given sum:

$$S_n=\sum_{k=0}^n\left(\frac{1}{k+1}{n \choose k} \right)$$
 
Mathematics news on Phys.org
MarkFL said:
Evaluate the given sum:

$$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}$.
 
caffeinemachine said:
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
 
MarkFL said:
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. :o

And what was your solution. I'd be interested in a pre-calculus solution.
 
caffeinemachine said:
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. :o

And what was your solution. I'd be interested in a pre-calculus solution.

You should get:

$$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)
 
MarkFL said:
You should get:

$$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.
 
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)
 
Here's my solution:

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}$$
 
Back
Top