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?

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*}

