5
$\begingroup$

$\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.

  • 0
    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.2011-11-22
  • 0
    sorry ………………...2011-11-22
  • 0
    This is much better, thank you for editing. I have upvoted your question.2011-11-22
  • 0
    It is likely that the problem lies with the translation into English of a very polite way of asking a question.2011-11-22

2 Answers 2