1
$\begingroup$

A problem I'm trying to figure out asks that I use the binomial theorem (or any other method I want) to evaluate $\sum_{k=0}^n \frac{1}{k+1} {n \choose k}$ in closed form.

The binomial theorem stated in my textbook: $(1+x)^n = {n\choose 0}+{n\choose 1}x+{n\choose 2}x^2+...+{n\choose k}x^k+...+{n\choose n}x^n$

I think the idea behind evaluating the summation to closed form is to perform some manipulation on the binomial theorem until it basically looks like what I want. My textbook only gives simplistic examples, like showing that $ \sum_{k=0}^n {n \choose k}$ by setting $x=1$. This doesn't really give me a good sense of how to do this problem.

Could I please have a hint?

$\endgroup$
  • 4
    $\begingroup$ Integrate, and see what happens. $\endgroup$ – Lucian Sep 21 '14 at 17:05
  • $\begingroup$ OK, this has gotten me really close to the answer's below. I'm trying to remember how integration works (haven't done any math in a long time), I'm trying to figure out why the constant from integrating = -1 $\endgroup$ – GrinReaper Sep 21 '14 at 17:16
  • $\begingroup$ See also How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $? $\endgroup$ – Martin Sleziak Jan 15 '17 at 9:13
5
$\begingroup$

Lucian's comment is perfectly fine. As an alternative, a nice old trick: $$\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\binom{n+1}{k+1}$$ hence: $$\sum_{k=0}^{n}\frac{1}{k+1}\binom{n}{k}=\frac{1}{n+1}\sum_{k=1}^{n+1}\binom{n+1}{k}=\frac{2^{n+1}-1}{n+1}.$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#66f}{\large\sum_{k = 0}^{n}{1 \over k+1}{n \choose k}}& =\sum_{k = 0}^{n}{n \choose k}\ \overbrace{\pars{\int_{0}^{1}t^{k}\,\dd t}} ^{\ds{=\ \color{#c00000}{1 \over k + 1}}}\ =\ \int_{0}^{1}\bracks{\sum_{k = 0}^{n}{n \choose k}t^{k}}\,\dd t =\int_{0}^{1}\pars{1 + t}^{n}\,\dd t \\[3mm]&=\left.{\pars{1 + t}^{n + 1} \over n + 1} \right\vert_{\, t\ =\ 0}^{\, t\ =\ 1} ={\pars{1 + 1}^{n + 1} - \pars{1 + 0}^{n + 1} \over n + 1} =\color{#66f}{\large{2^{n + 1} - 1 \over n + 1}} \end{align}

$\endgroup$
  • $\begingroup$ This raises a few questions. I guess I'll start with just this one why integrate t^k over 0 to 1? $\endgroup$ – GrinReaper Sep 22 '14 at 3:41
  • $\begingroup$ The choice of those limits allows you to set up the series that you want to sum. $\endgroup$ – Sherlock Holmes Sep 22 '14 at 4:11
  • $\begingroup$ I can see that by integrating over 0 to 1, I get end up with the result I want (one that's consistent with all the different methods for getting the desired closed-form), but I don't understand how the numbers 0 and 1 in particular, have anything to do with the original series $\endgroup$ – GrinReaper Sep 22 '14 at 7:55
  • $\begingroup$ The integration in $\left(\,0,1\,\right)$ let's to introduce a well known result. Namely,$\sum_{k = 0}^{n}{n \choose k}t^{k} = \left(\,1 + t\,\right)^{n}$. In many situations, it's easier to reduce the series to an integral. I saw $\color{#00f}{\tt @Sherlock Holmes}$ already pointed out this fact. $\endgroup$ – Felix Marin Sep 23 '14 at 16:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.