9
$\begingroup$

I need to express $$1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$$ in a simplified form.

So I used the identity $$(1+x)^n=1 + \binom{n}{1}x + \binom{n}{2}x^2 + \dotsb + \binom{n}{n}x^n$$ Now on integrating both sides and putting $x=1$.

I am getting $$\frac{2^{n+1}}{n+1}$$ is equal to the given expression.But the answer in my book is $$\frac{2^{n+1}-1}{n+1}.$$ Where does that -1 term in the numerator come from?

$\endgroup$
  • $\begingroup$ Also you may want to consider using parentheses. There are some strange syntax related things in your question. $\endgroup$ – mathreadler Jul 3 '16 at 6:36
9
$\begingroup$

$$\int^{1}_{0} (1+x)^n dx=\frac{(1+x)^{n+1}}{n+1}\bigg|^{1}_{0}=\frac{(1+1)^{n+1}-(1+0)^{n+1}}{n+1}=\frac{2^{n+1}-1}{n+1}$$

With indefinite integrals, there is always a constant of integration walking around. Hence, we use definite integrals so that the equality is kept.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You could have written that the mistake of the OP was to use indefinite integrals. With indefinite integrals, there is always a constant of integration walking around. Hence, we use definite integrals so that the equality is kept. $\endgroup$ – H. Potter Jul 3 '16 at 7:51
  • $\begingroup$ you're right, I just thought he could get what I want to say. $\endgroup$ – Victor Chen Jul 3 '16 at 9:14
6
$\begingroup$

Note that $$\binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}$$

Therefore,

\begin{align} \sum_{k=0}^{n}\frac{1}{k+1}{n\choose k}&=\frac{1}{n+1}\sum_{k=0}^{n}\frac{n+1}{k+1}{n\choose k} \\&=\frac{1}{n+1}\sum_{k=0}^{n}{{n+1}\choose {k+1}} \\&=\frac{1}{n+1}\left [\sum_{k=0}^{n+1}{{n+1}\choose k}-1\right ] \\&=\frac{1}{n+1}\left (2^{n+1}-1\right ) \end{align}

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting that typesetting Large inline, e.g. $\Large {{n+1}\choose {k+1}}$ looks slightly different from a normal size standalone equation e.g. $${{n+1}\choose {k+1}}$$ or Large within a standalone equation, e.g. $$\Large {{n+1}\choose {k+1}}$$ $\endgroup$ – Hypergeometricx Jul 4 '16 at 16:02
4
$\begingroup$

Among $n+1$ people, a subset is randomly selected (i.e., each person will be in the subset or not with probability $1/2$). Then one person in the subset (if it is nonempty) is selected at random to win a prize. What's the probability that I (one of the $n+1$ people) win it?

There are $\binom{n}{k}$ ways to pick a subset of size $k+1$ that contains me; the probability of that subset is $\frac{1}{2^{n+1}}$, and the probability that I am the one selected is $\frac{1}{k+1}$. So the desired probability is $$ \frac{1}{2^{n+1}} \sum_{k=0}^n \frac{1}{k+1} \binom{n}{k}. \tag{1} $$ On the other hand, everyone out of the $n+1$ has an equal chance of winning, and there is only a $\frac{1}{2^{n+1}}$ chance of no one being selected, so the probability is $$ \frac{2^{n+1} - 1}{2^{n+1}} \cdot \frac{1}{n+1}. \tag{2} $$ Thus (1) and (2) are equal, and if we multiply by $2^{n+1}$ we get $$ \sum_{k=0}^n \frac{1}{k+1} \binom{n}{k} = \frac{2^{n+1} - 1}{n+1}. $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I suppose this is the combinatorial argument. Nice. $\endgroup$ – StubbornAtom Jul 3 '16 at 7:41
  • $\begingroup$ @StubbornAtom Yes, although it ceases to be purely combinatorial when I multiply by $2^{n+1}$ at the end :) $\endgroup$ – 6005 Jul 3 '16 at 7:45
1
$\begingroup$

Remember when you integrate both sides, there will be the constant of integration. You need to first find this constant of integration. That's where the $-1$ comes from. In actual fact, it is $\frac{-1}{n+1}$ but looks like $-1$ because it's been absorbed into the numerator.

You may like to try $x=0$ to find this $+C$ value...

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy