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?

  • 2
    $\begingroup$ The $q$-binomial at $(n,k)$ counts subspaces of dimension k in an n dimensional space over F_q. Use this. $\endgroup$ – Pedro Tamaroff Sep 25 '16 at 6:53
  • $\begingroup$ So, using that, the term $${n \choose k-1}_q$$ comes from fixing 1 basis element in all the k dimensional subspaces from the n+1 dimensional space. Then, to find all the possible k dimensional subspaces from the n dimensional space when we fix this element, we can change k-1 basis elements in any subspace, which we can choose from any of the n remaining elements (non-fixed) from the n+1 dimensional space, and so we have $${n \choose k-1}_q$$. Is this interpretation right for this part of the sum? $\endgroup$ – user372002 Sep 25 '16 at 8:10
  • $\begingroup$ For the other term I reallly don't know how to think about it. The $q^k$ confuses me a lot. Any help with this would be specially appreciated. Thanks! $\endgroup$ – user372002 Sep 25 '16 at 13:58
  • $\begingroup$ Why not expand the right term? $\endgroup$ – Noud Oct 1 '16 at 6:00
  • $\begingroup$ There are some typos in the bounty explanation; unfortunately, editing it is not possible. I hope it is clear though; if not, please do ask me. $\endgroup$ – zhoraster Feb 24 '17 at 9:52

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.

                                    enter image description here

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.

  • $\begingroup$ An excellent question! However, while this answers the OP, it doesn't qualify for bounty (I expected a subspace-counting argument). Anyway, thanks for sharing this! $\endgroup$ – zhoraster Feb 25 '17 at 18:06
  • $\begingroup$ @zhoraster: You're welcome! I'm aware of this aspect with respect to the bounty. Nevertheless I thought this combinatorial approach is interesting and could be placed as answer. Regards, $\endgroup$ – Markus Scheuer Feb 25 '17 at 18:11
  • $\begingroup$ An excellent answer, I meant :) $\endgroup$ – zhoraster Feb 25 '17 at 20:11
  • $\begingroup$ @zhoraster: Many thanks! :-) $\endgroup$ – Markus Scheuer Feb 25 '17 at 20:23

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.

                                    enter image description here

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

  • $\begingroup$ I have to digest this. $\endgroup$ – zhoraster Feb 27 '17 at 12:59
  • $\begingroup$ What do you mean by the "first dimension" being part of a subspace? $\endgroup$ – darij grinberg Mar 3 '17 at 2:11
  • $\begingroup$ @darijgrinberg: The first coordinate. In fact the intention was the same as in the other answer, but in my example a projection with the first coordinate discarded. $\endgroup$ – Markus Scheuer Mar 3 '17 at 7:24

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.
  • $\begingroup$ Magnificent! Exactly what I need, thanks! $\endgroup$ – zhoraster Mar 3 '17 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.