alternative proof to induction, binomial sum identity 
$\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.
 A: $\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}.$$
A: Another way is to use snake oil:
$\begin{align}
\sum_{n \ge 1} z^n \sum_{0 \le q \le k} \binom{n + q - 1}{n - 1}
  &= \sum_{0 \le q \le k} 
       z^{1 - q} \sum_{n \ge 1} \binom{n + q - 1}{q} z^{n + q - 1} \\
  &= \sum_{0 \le q \le k}
       z^{1 - q} \sum_{s \le 0} \binom{s}{q} z^s \\
  &= \sum_{0 \le q \le k}
       z^{1 - q} \frac{z^q}{(1 - z)^{q + 1}} \\
  &= \frac{z}{1 - z} \sum_{0 \le q \le k} (1 - z)^{-q} \\
  &= \frac{z}{1 - z} \frac{1 - (1 - z)^{-k - 1}}{1 - (1 - z)^{-1}} \\
  &= \frac{1}{(1 - z)^{k + 1}} - 1
\end{align}$
Now we want the coefficient of $z^n$:
$\begin{align}
[z^n] \frac{1}{(1 - z)^{k + 1}}
  &= (-1)^n \binom{-k - 1}{n} \\
  &= \binom{n + k + 1 - 1}{k + 1 - 1} \\
  &= \binom{n + k}{k} \\
  &= \binom{n + k}{n}
\end{align}$
