Combinatorial proof of q-binomial recurrence relation I have no idea how to proof combinatorially the following recurrence relation:
$${n+1\choose k}_q = q^k {n \choose k}_q + {n \choose k-1}_q$$
Could anyone guide me through a combinatorial proof or give me hints on how to prove it?
 A: Here  is  a  combinatorial approach based  upon lattice paths.  We consider paths of length $m+n$ starting from $(0,0)$ leading to $(m,n)$ with steps $(1,0)$ and   $(0,1)$. A typical path is given below.
                                    
We classify paths by the number of squares which are enclosed between the path, the $x$-axis and the line $x=m$. In the given figure  we can see $13$ enclosed squares.

We denote with $p_i(m,n)$ the number of paths of length $m+n$ in a rectangle with sides $m$ and $n$ which enclose $i$ squares and show the following is valid
  \begin{align*}
p_i(m,n)&=p_i(m-1,n)+p_{i-m}(m,n-1)&m,n\geq 0 \text{ and } \left(m,n\right) \neq \left(0,0\right)\tag{1}\\
p_i(0,0)&= \begin{cases}1, & \text{ if } i = 0;\\ 0, & \text{ otherwise} \end{cases}\\
p_i(m,n)&=0& m<0\text{ or }n<0
\end{align*}

We argue as follows


*

*Each path counted by  $p_i(m,n)$ starts either with step $(1,0)$ or with $(0,1)$.

*If   it starts with  $(1,0)$   there is no square which is  enclosed in the first column of the rectangle, and we have to  consider   all paths from $(1,0)$ to $(m,n)$ which enclose $i$ squares. This is counted by $p_i(m-1,n)$.

*If it starts with $(0,1)$ then it will enclose all $m$ squares in the bottom row. The number of all these paths is $p_{i-m}(m,n-1)$.  We take $n-1$  since we have already  considered the bottom row.

*The  boundary condition $p_i(0,0)= \begin{cases}1, & \text{ if } i = 0;\\ 0, & \text{ otherwise} \end{cases}$ indicates there is exactly one path of length zero from $(0,0)$ to $(0,0)$, and that it encloses no square. The other boundary conditions indicate there are no lattice paths from $(0,0)$ to $(m,n)$ with $m<0$ or $n<0$ since we can only do steps in $(1,0)$ direction or in  $(0,1)$ direction.

We define a generating function $P_{m,n}(q)$ with coefficients $p_i(m,n)$ via
  \begin{align*}
P_{m,n}(q)=\sum_{i\geq 0}p_i(m,n)q^i
\end{align*}
The generating function $P_{m,n}(q)$ is in fact  a  polynomial, since   $p_i(m,n)=0$ for $i>mn$.   

Using the coefficient of operator $[q^i]$ to denote the coefficient of $q^i$ in a series we obtain according to (1)
\begin{align*}
[q^i]P_{m,n}(q)=[q^i]P_{m-1,n}(q)+[q^{i-m}]P_{m,n-1}(q)\tag{2}
\end{align*}
whenever $m,n\geq 0$ and $\left(m,n\right) \neq \left(0,0\right)$.

Since the coefficient of operator fulfills $[q^{i-m}]A(q)=[q^i]q^mA(q)$, we obtain from (2)
  \begin{align*}
P_{m,n}(q)&=P_{m-1,n}(q)+q^mP_{m,n-1}(q) \qquad \qquad m,n\geq 0 \text{ and } \left(m,n\right) \neq \left(0,0\right) \tag{3}\\
P_{0,0}(q)&=1\\
P_{m,n}(q)&=0\qquad\qquad m<0\text{ or } n<0
\end{align*}

The recurrence relation (3) is the same relation as it is given for the $q$-binomial coefficient. 
We can therefore set $P_{m,n}(q)=\binom{m+n}{m}_q$ and conclude:

The $q$-binomial coefficient $\binom{m+n}{m}_q$ can be interpreted as generating function $P_{m,n}(q)$
  \begin{align*}
\color{blue}{\binom{m+n}{m}_q=P_{m,n}(q)=\sum_{i\geq 0}p_i(m,n)q^i}
\end{align*}
  counting the number of all lattice paths in an $m\times n$ rectangle with the coefficient of $q^i$ giving the number of lattice paths which enclose $i$ squares. The recurrence relation according to (3) is given by
  \begin{align*}
\binom{m+n}{m}_q=\binom{m+n-1}{m-1}_q+q^m\binom{m+n-1}{m}_q\tag{4}
\end{align*}

We can transform the relation (4) by setting
\begin{align*}
m&\longrightarrow k\\
n&\longrightarrow n+1-k
\end{align*}

and obtain
\begin{align*}
\binom{n+1}{k}_q=\binom{n}{k-1}_q+q^k\binom{n}{k}_q
\end{align*}

$$ $$

Note: The figure  showing    a  lattice path gives rise to a different combinatorial interpretation. We consider the enclosed rectangles as Young diagram representing a partition of an integer. Here we have
  \begin{align*}
13=5+5+2+1
\end{align*}
From this point of view $p_i(m,n)$ can be interpreted as the number of partitions of $i$ with largest part at most $m$ and with at most $n$ parts.
A nice introductory presentation of this combinatorial approach is presented in chapter 6 of Topics in Algebraic Combinatorics  by R.P. Stanley.

A: Here is   a  combinatorial approach to show the $q$-binomial identity
\begin{align*}
\binom{n}{k}_q=q^k\binom{n-1}{k}_q+\binom{n-1}{k-1}_q\tag{1}
\end{align*}
by  counting $k$-dimensional subspaces   of  the vector space $\mathbb{F}_q^n$ over the finite field $\mathbb{F}_q$.
This is done in two steps. At first we show the number of subspaces is $\binom{n}{k}_q$. Then we use the figure showing a lattice path from the other answer as inspiration and prove (1).

Let $q$ be a prime power and consider the $\mathbb{F}_q$-vector space
  $$\mathbb{F}_q^n=\{(\alpha_1,\ldots,\alpha_n):\alpha_i\in\mathbb{F}_q\}$$
  Let  $G(n,k)$ equal the number of $k$-dimensional subspaces of $\mathbb{F}_q^n$.

$$ $$

Step 1: $G(n,k)=\binom{n}{k}_q$
For the proof of this, we WLOG assume $0 \leq k \leq n$, as the claim is otherwise trivial.
Let $N=N(n,k)$ be the number of ordered $k$-tuples $\{v_1,\ldots,v_k\}$ of linearly independent vectors of $\mathbb{F}_q^n$.
We  may choose $v_1$ in $q^n-1$ ways, then $v_2$ in $q^n-q$ ways, and so on, yielding
  \begin{align*}
N=(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})\tag{2}
\end{align*}
We may also count $N=N(n,k)$ in a different way. We choose  $(v_1,\ldots,v_k)$  by  first  selecting  a $k$-dimensional subspace $W$  of $\mathbb{F}_q^n$  in $G(n,k)$ ways, and then choosing $v_1\in W$ in $q^k-1$ ways, $v_2\in W$ in $q^k-q$ ways, and so on. Hence
  \begin{align*}
N=G(n,k)(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})\tag{3}
\end{align*}
We obtain from (2) and (3)
  \begin{align*}
G(n,k)&=\frac{(q^n-1)(q^n-q)\cdots (q^n-q^{k-1})}{(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})}\\
&=\frac{(n!)_q}{(k!)_q((n-k)!)_q}\\
&=\binom{n}{k}_q
\end{align*}
  and the claim follows.
Note: This is the proof of Proposition 1.3.18 in the first edition of Enumerative Combinatorics by R.P. Stanley.

$$ $$

Step 2: The $q$-binomial identity
Let's take a look at the $q$-binomial      identity 
  \begin{align*}
\binom{n}{k}_q=q^k\binom{n-1}{k}_q+\binom{n-1}{k-1}_q
\end{align*}

We know $\binom{n}{k}_q$ is the number of $k$-dimensional subspaces of the $n$-dimensional vector space $\mathbb{F}_q^n$. If we consider the figure showing the lattice path, we partitioned the paths according to the first step $(1,0)$ resp. $(0,1)$. We will do here something similar.
                                    

We fix a dimension and partition the number of $k$-dimensional subspaces according to it. Let's say when considering an $n$-tuple $(\alpha_1,\ldots,\alpha_n)\in\mathbb{F}_q^n$, we fix the first dimension indexed with $1$.
When we select a $k$-dimensional subspace then there are two possibilities with respect to this fixed dimension.
  
  
*
  
*The dimension is part of the $k$-dimensional subspace
  
*The dimension is not part of the $k$-dimensional subspace and therefore part of the $n-k$-dimensional complement space.

$$ $$

Case 1: The dimension is part of the $k$-dimensional subspace
  
  
*
  
*This corresponds to step $(1,0)$. We observe, that one dimension of a $k$-dimensional subspace is already consumed, leaving $k-1$ dimensions which are to select out of $n-1$ dimensions. So, the number of $k-1$ dimensional subspaces which is to select is
  \begin{align*}
\binom{n-1}{k-1}_q
\end{align*}
  
  
  Case 2: The dimension is not part of the $k$-dimensional subspace.
  
  
*
  
*This corresponds to step $(0,1)$. The fixed dimension is now part of the $n-k$-dimensional complement space.
We still have to select $k$ dimensions for the $k$-dimensional subspace, but now out of $n-1$ dimensions.
This implies that the entry with index $1$ has no influence to the $k$-dimensional subspace and we are free to put any of $q$ values for it. Since we select a $k$-dimensional subspace where the first index in each of the $k$ base vectors is free to select, we have $q^k$ possibilities to do so, giving a total of
  \begin{align*}
q^k\binom{n-1}{k}_q
\end{align*}
and the claim (1) follows.

$$ $$

Example: $\mathbb{F}_2^3$
To better see what's going on in case 1 and case 2 we look at a small example. Here we set 
  $$q=2,n=3,k=2$$
  and consider
  \begin{align*}
\binom{3}{2}_2=\color{blue}{2^2}\cdot\binom{2}{2}_2+\binom{2}{1}_2=\color{blue}{4}\cdot 1+3=7
\end{align*}

We  have 
\begin{align*}
\mathbb{F}_2^3=\left\{
\begin{pmatrix}0\\0\\0\end{pmatrix},
\begin{pmatrix}1\\0\\0\end{pmatrix},
\begin{pmatrix}0\\1\\0\end{pmatrix},
\begin{pmatrix}1\\1\\0\end{pmatrix},
\begin{pmatrix}0\\0\\1\end{pmatrix},
\begin{pmatrix}1\\0\\1\end{pmatrix},
\begin{pmatrix}0\\1\\1\end{pmatrix},
\begin{pmatrix}1\\1\\1\end{pmatrix}
\right\}
\end{align*}
We now list the $3$ subspaces which belong to case $1$ and the $4$ subspaces which belong to case $2$. To simplify the notation and save space, we do not write the zero vector and omit commas. We obtain

Case 1:
  The entries with index $1$ are part of the two-dimensional subspace.
  \begin{align*}
W_1=\left\{
\begin{pmatrix}1\\0\\0\end{pmatrix}
\begin{pmatrix}0\\1\\0\end{pmatrix}
\begin{pmatrix}1\\1\\0\end{pmatrix}
\right\}
&\qquad     W_2=\left\{
\begin{pmatrix}1\\0\\0\end{pmatrix}
\begin{pmatrix}0\\0\\1\end{pmatrix}
\begin{pmatrix}1\\0\\1\end{pmatrix}
\right\}\\
W_3=\left\{
\begin{pmatrix}1\\0\\0\end{pmatrix}
\begin{pmatrix}0\\1\\1\end{pmatrix}
\begin{pmatrix}1\\1\\1\end{pmatrix}
\right\}
\end{align*}

$$ $$

Case 2:
  The entries with index $1$ are not part of the two-dimensional subspace. To better identify the four subspaces see the blue colored components $\color{blue}{00},\color{blue}{01},\color{blue}{10}$ and $\color{blue}{11}$.
\begin{align*}
W_4=\left\{
\begin{pmatrix}\color{blue}{0}\\1\\0\end{pmatrix}
\begin{pmatrix}\color{blue}{0}\\0\\1\end{pmatrix}
\begin{pmatrix}0\\1\\1\end{pmatrix}
\right\}
&\qquad W_5=\left\{
\begin{pmatrix}\color{blue}{0}\\1\\0\end{pmatrix}
\begin{pmatrix}\color{blue}{1}\\0\\1\end{pmatrix}
\begin{pmatrix}1\\1\\1\end{pmatrix}
\right\}\\
W_6=\left\{
\begin{pmatrix}\color{blue}{1}\\1\\0\end{pmatrix}
\begin{pmatrix}\color{blue}{0}\\0\\1\end{pmatrix}
\begin{pmatrix}1\\1\\1\end{pmatrix}
\right\}
&\qquad W_7=\left\{
\begin{pmatrix}\color{blue}{1}\\1\\0\end{pmatrix}
\begin{pmatrix}\color{blue}{1}\\0\\1\end{pmatrix}
\begin{pmatrix}0\\1\\1\end{pmatrix}
\right\}
\end{align*}

A: As proposed, I define $\binom nk_q$ as the number of $k$-dim subspaces of $n$-dim space over the field $\mathbb Z_q$.
Take a $k$-dim subspace S of a given $(n+1)$-dim space $\mathbb Z_q^{n+1}$ and take its projection to $\mathbb Z_q^n$ (last coordinate discarded). Denote the projected $S$ as $S'$. There are two cases: 


*

*$\dim(S') = \dim(S)-1$. In this case, $S'$ uniquely determines $S$: $S$ is the preimage of $S'$ in the projection. So it corresponds to the second summand $\binom n{k-1}_q$ since it counts the number of all possible $(k-1)$-dim subspaces $S'$.

*$\dim(S') = \dim(S)$. In this case we have lost one information about $S$ -- the last coordinate at every point. This coordinate is described by a linear form $S'\to \mathbb Z_q$ and there are $q^k$ of them since $S'$ is $k$-dimensional. And similarly as before, $\binom nk_q$ counts the number of possible $S'$. So there are $\binom nk_q\cdot q^k$ all possible original $S$ in this case.

