# Using binomial theorem to evaluate summation $\sum_{k=0}^n \frac{1}{k+1} \binom nk$ in closed form

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?

• Integrate, and see what happens. Commented Sep 21, 2014 at 17:05
• 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 Commented Sep 21, 2014 at 17:16
• Commented Jan 15, 2017 at 9:13

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}.$$
$$\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 \\[3mm] & =\int_{0}^{1}\pars{1 + t}^{n}\,\dd t = \left.{\pars{1 + t}^{n + 1} \over n + 1} \right\vert_{\, t\ =\ 0}^{\, t\ =\ 1} \\[3mm] & = {\pars{1 + 1}^{n + 1} - \pars{1 + 0}^{n + 1} \over n + 1}\ =\ \bbox[15px,border:1px solid navy]{\color{#44f}{\large{2^{n + 1} - 1 \over n + 1}}} \end{align}
• 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. Commented Sep 23, 2014 at 16:47
$$\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}$$