Combinatorial proof of q-binomial recurrence relation

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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:

1. $\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'$.
2. $\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.