0
$\begingroup$

Is is possible to find the sum of a binomial coefficient series like: $\sum_{k=n}^{r}\dbinom{k}{n}$? Just a random thought.

$\endgroup$
  • $\begingroup$ If you have meant $\displaystyle\sum_{r=1}^n r\binom nr$ $$\displaystyle r\binom nr=r\dfrac{n\cdot(n-1)!}{r\cdot(r-1)!\{n-1-(r-1)\}!}=n\binom{n-1}{r-1}$$ $\endgroup$ – lab bhattacharjee Apr 7 '15 at 18:57
  • 1
    $\begingroup$ ${k \choose n} = 0$ if $k < n$, $1$ if $k=n$. Maybe you'd rather do $$\sum_{k=n}^r {k \choose n}$$ $\endgroup$ – Robert Israel Apr 7 '15 at 19:15
  • $\begingroup$ yeah yeah im so sorry... i didnt notice the flaw in my question $\endgroup$ – user220382 Apr 7 '15 at 19:18
2
$\begingroup$

$$ \sum_{k=n}^r {k \choose n} = \dfrac{r+1-n}{n+1} {r+1 \choose n} $$ Prove by induction on $r$.

EDIT: Actually this can be written as $${r+1 \choose n+1}$$ in which form it has a nice combinatorial interpretation. Suppose you want to have $r+1$ objects numbered $1$ to $r+1$, and you want to choose $n+1$ of them. How many ways to do it? Divide into cases according to the highest-numbered object chosen. If the highest-numbered object chosen has number $k+1$, the remaining $n$ objects can be chosen from $1,\ldots, k$ in ${k \choose n}$ ways, where of course we need $k \ge n$. Therefore $$ {{r+1} \choose {n+1}} = \sum_{k=n}^r {k \choose n}$$

$\endgroup$
  • $\begingroup$ Please give a proof without induction.Or provide the source of the formula you stated. $\endgroup$ – user220382 Apr 7 '15 at 19:21
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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

\begin{align} \color{#f00}{\sum_{k = n}^{r}{k \choose n}} & = \sum_{k = n}^{r}\overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{k} \over z^{n + 1}}\, {\dd z \over 2\pi\ic}}^{\ds{{k \choose n}}} = \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}}\sum_{k = n}^{r}\, \pars{1 + z}^{k}{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}} \pars{1 + z}^{n}\,{\pars{1 + z}^{r - n + 1} - 1 \over \pars{1 + z} - 1} \,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{r + 1} \over z^{n + 2}} \,{\dd z \over 2\pi\ic} - \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n} \over z^{n + 2}} \,{\dd z \over 2\pi\ic} = {r + 1 \choose n + 1}\ -\ \overbrace{{n \choose n + 1}}^{\ds{=\ 0}} \\[3mm] & = \color{#f00}{{r + 1 \choose n + 1}} \end{align}

$\endgroup$

Your Answer

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