# $\sum_{k=0}^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}=?$

I was asked to find a closed formula for the sum

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

could anyone give me an advice on how to get started?

-
Hint: expand the binomal coefficient $\binom nk$ using factorials. – Tom-Tom Feb 7 '14 at 9:08
We get $$\sum_{k=0}^{n}\frac{n!}{(k+2)!(n-k)!}$$ – Oria Gruber Feb 7 '14 at 9:11
That's correct. Now this almost looks like another binomial coefficient, doesn't it ? Try to write it as a binomial coefficient by multiplying it by something that depends on $n$ only. – Tom-Tom Feb 7 '14 at 9:14
gotcha :D thanks – Oria Gruber Feb 7 '14 at 9:17

$$=\sum_{k=0}^{n}\frac{k!}{k!(k+1)(k+2)}\binom{n}{k} =\sum_{k=0}^{n}\frac{k!}{(k+2)!}\cdot\frac{n!}{k!(n-k)!} \\=\sum_{k=0}^{n}\frac{n!}{(k+2)!(n-k)!} \\=\frac{1}{(n+1)(n+2)}\sum_{k=0}^{n}\frac{(n+2)!}{(k+2)!(n-k)!} \\=\frac{1}{(n+1)(n+2)}\sum_{k=0}^{n}\binom{n+2}{k+2}$$ then you can complete using $(1+x)^n=\sum {{n}\choose{k}} x^k$

-
I think you meant $\sum \binom{n}{k}x^k$ and wrote $r$ by mistake, right? – Oria Gruber Feb 7 '14 at 9:22
yes @OriaGruber – Sameh Shenawy Feb 7 '14 at 9:23

$\newcommand{\+}{^{\dagger}} \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{\down}{\downarrow} \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{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \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{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $$\mbox{Lets consider}\quad\fermi\pars{x}\equiv \sum_{k = 0}^{n}{x^{k + 2} \over \pars{k + 1}\pars{k + 2}}\,{n \choose k}\,,\quad \fermi\pars{0} =0\,,\quad\fermi\pars{1} = {\large ?}$$

$$\fermi'\pars{x}= \sum_{k = 0}^{n}{x^{k + 1} \over k + 1}\,{n \choose k}\,,\qquad \fermi'\pars{0} = 0$$

$$\fermi''\pars{x}= \sum_{k = 0}^{n}x^{k}{n \choose k}=\pars{1 + x}^{n}\qquad\imp\qquad \fermi'\pars{x}={\pars{1 + x}^{n + 1} - 1\over n + 1}$$

$$\imp\qquad\fermi\pars{x}= {1 \over n + 1}\,{\pars{1 + x}^{n + 2} - 1 \over n + 2} - {x \over n + 1}$$

$$\fermi\pars{1} =\color{#66f}{\large\sum_{k = 0}^{n}{1 \over \pars{k + 1}\pars{k + 2}}\, {n \choose k} ={2^{n + 2} - n - 3 \over \pars{n + 1}\pars{n + 2}}}$$

-
Beautiful proof. – MathFacts Jul 20 '14 at 4:09
@MathFacts I was wondering why no answer puts clearly and visible the final result. Thanks. – Felix Marin Jul 20 '14 at 7:41
I downloaded metmat-2003 from your site; Glad to know that Venezuela has a great mathematician. I am Brazilian and I have a lot to learn. – MathFacts Jul 20 '14 at 7:47

Hint
$$\sum_{k=0}^{n}\binom{n}{k}x^k = (1+x)^n$$ Integrate twice both rhs and lhs with respect to $x$ and when finished, plug $x=1$ in your result.

-
There is no need of integration here. – Tom-Tom Feb 7 '14 at 9:15
In "mathematic" house are many mansions (adaptation of John 14:2) – Claude Leibovici Feb 7 '14 at 9:19
I do agree with that, but one may enter into the house without keys to all mansions. – Tom-Tom Feb 7 '14 at 14:35

Sure - you know that $(1 + x)^n = \sum_{k=0} ^n \binom{n}{k} x^k$ from which it follows that $$\frac{(1+x)^{n+1}}{n+1} = \int (1 + x)^n \, \mathrm{d}x = \int \sum_{k=0} ^n \binom{n}{k} x^k \, \mathrm{d}x = \sum_{k=0} ^n \binom{n}{k} \int x^k \, \mathrm{d}x = \sum_{k=0} ^n \binom{n}{k} \frac{x^{k+1}}{k+1} .$$ Based on what I've shown, you can iterate on this method, and allow $x$ to become a certain number, which should give you the closed form you are seeking.

-

Start with $(1+x)^n=\sum {{n}\choose{k}} x^k$ . If you integrate this twice wrt x you will get something close to what you are after.

-
You won by half a second ! Cheers. – Claude Leibovici Feb 7 '14 at 9:14