2
$\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$
3
  • 4
    $\begingroup$ Integrate, and see what happens. $\endgroup$
    – Lucian
    Commented Sep 21, 2014 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
    Commented Sep 21, 2014 at 17:16
  • $\begingroup$ See also How can I compute $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $? $\endgroup$ Commented Jan 15, 2017 at 9:13

3 Answers 3

6
$\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$
2
$\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 \\[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}

$\endgroup$
4
  • $\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
    Commented Sep 22, 2014 at 3:41
  • $\begingroup$ The choice of those limits allows you to set up the series that you want to sum. $\endgroup$ Commented Sep 22, 2014 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
    Commented Sep 22, 2014 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$ Commented Sep 23, 2014 at 16:47
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .