Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\displaystyle \sum_{q=0}^{k} \begin{pmatrix}n-1+q\\ n-1 \end{pmatrix} = \begin{pmatrix}n+k\\n \end{pmatrix} $

induction

$\begin{pmatrix}n \\ k \end{pmatrix} := \frac{n!}{(n-k)!k!}$

Beginning of induction : $k=0 \rightarrow \begin{pmatrix} n-1 \\ n-1 \end{pmatrix} = \begin{pmatrix} n \\ n \end{pmatrix} = 1 $

Induction step : $k\rightarrow k+1: \sum_{q=0}^{k+1} \begin{pmatrix} n-1+q\\n-1 \end{pmatrix} = (\sum_{q=0}^{k} \begin{pmatrix} n-1+q\\n-1 \end{pmatrix}) + \pmatrix{n-1+k+1\\n-1} $

$\displaystyle = \begin{pmatrix}n+k \\ n \end{pmatrix} + \begin{pmatrix} n+k \\ n-1 \end{pmatrix} = \frac{(n+k)!}{k!(n)!}+ \frac{(n+k)!}{(k+1)!(n-1)!} =$

$\displaystyle =\frac{(n+k)!(k!n!+(k+1)k!(n-1)!}{k!n!(k+1)!(n-1)!} = \frac{(n+k)!(n+k+1)}{n!(k+1)!} = \begin{pmatrix}n+k+1 \\ n \end{pmatrix}$


Do you know any other way to show this? Please do tell.

share|improve this question
    
Your question is phrased in an inappropriate manner. No one here has to offer anything to you if they don't want to - ask politely. –  Zev Chonoles Nov 22 '11 at 18:15
    
sorry ………………... –  VVV Nov 22 '11 at 18:17
    
This is much better, thank you for editing. I have upvoted your question. –  Zev Chonoles Nov 22 '11 at 18:23
    
It is likely that the problem lies with the translation into English of a very polite way of asking a question. –  André Nicolas Nov 22 '11 at 18:24

1 Answer 1

$\binom{n+k}{n}$ is the number of ways of choosing $n$ objects from $n+k$ possibilities.

In order to select $n$ objects out of $n+k$ possibilities, we can also proceed as follows: number the objects from $1$ throught $n+k$. First, pick the object with the largest number that you will select; it must be numbered somewhere between $n$ and $n+k$ (otherwise, you cannot pick $n$ objects total); say it is numbered $n+q$, with $q\in\{0,\ldots,k\}$. Then you still have to pick $n-1$ objects from the first $n+q-1$ objects; this can be done in precisely $\binom{n+q-1}{n-1}$ ways.

Since you can do this for each value of $q\in\{0,\ldots,k\}$, adding up these possibilities will result in a selection of $n$ objects from $n+k$ possibilities; that is, $$\sum_{q=0}^{k}\binom{n+q-1}{n-1} = \binom{n+k}{n}.$$

share|improve this answer
    
Arturo Magidin, Thank You. –  VVV Nov 22 '11 at 21:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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