Partitions in a \((k{+}1) \times (n{-}k)\) box split into those with \(\le k\) parts and those with exactly \(k{+}1\) parts. The latter biject with partitions in a \((k{+}1) \times (n{-}k{-}1)\) box via “removing a column” (subtracting 1 from each of the \(k{+}1\) parts), with size decreased by \(k{+}1\) (giving the factor \(q^{k+1}\)).

The forward bijection subtracts 1 from each of the \(k{+}1\) parts (and filters zeros); the inverse adds 1 to each part and pads with 1s to reach exactly \(k{+}1\) parts. Injectivity follows from the recovery lemma for filtered multiset subtraction; surjectivity is verified directly.

Both definitions satisfy the same boundary conditions (\(\binom {n}{0}_q = 1\), \(\binom {n}{k}_q = 0\) for \(k {\gt} n\)) and the same \(q\)-Pascal recurrence. By strong induction on \(n\) with case analysis on \(k\), the two definitions agree.

By induction on \(n\), splitting the monotone functions into those starting at 0 and those starting at a positive value, using the bijections \(\mathrm{dropFirst}\)/\(\mathrm{prependZero}\) and \(\mathrm{shiftDown}\)/\(\mathrm{shiftUp}\).

Via the bijection from monotone \(k\)-tuples in \(\{ 0,\ldots ,n{-}k\} \) to \(k\)-element subsets of \(\{ 1,\ldots ,n\} \): \((i_1,\ldots ,i_k) \mapsto \{ i_1{+}1, i_2{+}2, \ldots , i_k{+}k\} \). For \(k {\gt} n\), both sides are 0.

By strong induction on \(n\), using the \(q\)-Pascal recurrence and the splitting identity \([n{+}1]_q = [k{+}1]_q + q^{k+1} [n{-}k]_q\).

When expanding the product \(\prod _{i=1}^{n}\left( a_{i}+b_{i}\right) =\left( a_{1}+b_{1}\right) \left( a_{2}+b_{2}\right) \cdots \left( a_{n}+b_{n}\right) \), you obtain a sum of \(2^{n}\) terms, each of which is a product of one addend chosen from each of the \(n\) sums \(a_{1}+b_{1},a_{2}+b_{2},\ldots ,a_{n}+b_{n}\). This is precisely what the right hand side of 12 is. A rigorous proof can be found in [ Grinbe15 , Exercise 6.1 (a) ] . The formal proof follows by induction on \(n\), using the distributive law at each step.

By induction on \(n\), using the \(q\)-Pascal recurrence. The subsets of \(\{ 0,\ldots ,n\} \) of size \(k{+}1\) split into those containing \(n\) and those not containing \(n\). The key algebraic identity is \(q^k \binom {n}{k+1}_q + q^n \binom {n}{k}_q = q^k \binom {n}{k}_q + q^{k+1} \cdot q^k \binom {n}{k+1}_q\), which is proved by induction using algebraic manipulation.

By induction on \(n\), using the \(q\)-Pascal recurrence and algebraic manipulation.

Let \(\left[ n\right] \) denote the set \(\left\{ 1,2,\ldots ,n\right\} \). We have

by Lemma 2.164, applied to \(L=K\left[ q\right]\), \(a_{i}=aq^{i-1}\) and \(b_{i}=b\). Now,

(since \(\prod _{i\in S}q^{i-1} = q^{\operatorname {sum}S - |S|}\) and \(|[n]\setminus S| = n - k\)). Using \(q^{\operatorname {sum}S-k} = q^{\operatorname {sum}S-(1+2+\cdots +k)} \cdot q^{k(k-1)/2}\) (since \(1+2+\cdots +(k-1) = k(k-1)/2\)), we obtain

(Here, the underbrace equality follows from Proposition 2.140 (b).) This proves Theorem 2.167.

Specializing Theorem 2.167 at \(q = 1\): the LHS becomes \((a+b)^n\) and each \(\binom {n}{k}_1 = \binom {n}{k}\).

By induction on \(k\). The base case is trivial. For the inductive step: \(b \cdot a^{k+1} = b \cdot a^k \cdot a = \omega ^k (a^k b) \cdot a = \omega ^k \cdot a^k \cdot (ba) = \omega ^k \cdot a^k \cdot \omega (ab) = \omega ^{k+1}(a^{k+1} b)\).

By induction on \(n\). The base case \(n=0\) is trivial. For the inductive step, write \((a+b)^{n+1} = (a+b) \cdot (a+b)^n\) and apply the induction hypothesis to \((a+b)^n\). Distribute \((a+b)\) over the sum. The key step is the relation \(b \cdot a^k = \omega ^k \cdot a^k \cdot b\), which follows from \(ba = \omega ab\) by induction on \(k\) (proved in Lemma 2.169). After reindexing and combining terms, the coefficients match via the \(q\)-Pascal recurrence \(\binom {n+1}{k+1}_\omega = \binom {n}{k}_\omega + \omega ^{k+1}\binom {n}{k+1}_\omega \).

The fiber over \(W\) is in bijection with the set of linearly independent \(k\)-tuples in \(W\). Since \(W\) is \(k\)-dimensional, applying Lemma 2.174 (with \(W\) in place of \(V\), and \(k\) in place of \(n\)) gives the count \(\prod _{i=0}^{k-1}(|F|^k - |F|^i)\).

We prove both directions:

\(\Longrightarrow :\) Assume that the \(k\)-tuple \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \) is linearly independent. Let \(i\in \left\{ 1,2,\ldots ,k\right\} \). If we had \(v_{i}\in \operatorname {span}\left( v_{1},v_{2},\ldots ,v_{i-1}\right) \), then we could write \(v_{i}\) in the form \(v_{i}=\alpha _{1}v_{1}+\alpha _{2}v_{2}+\cdots +\alpha _{i-1}v_{i-1}\) for some coefficients \(\alpha _{1},\alpha _{2},\ldots ,\alpha _{i-1}\in F\), and therefore \(\alpha _{1}v_{1}+\cdots +\alpha _{i-1}v_{i-1}+(-1)v_{i}+0v_{i+1}+\cdots +0v_{k}=\mathbf{0}\), which would be a nontrivial linear dependence relation (since \(v_{i}\) appears with the nonzero coefficient \(-1\)); this would contradict the linear independence of \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \). Hence, \(v_{i}\notin \operatorname {span}\left( v_{1},v_{2},\ldots ,v_{i-1}\right)\).

\(\Longleftarrow :\) Assume that each \(i\in \left\{ 1,2,\ldots ,k\right\} \) satisfies \(v_{i}\notin \operatorname {span}\left( v_{1},v_{2},\ldots ,v_{i-1}\right) \). Assume for contradiction that the \(k\)-tuple \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \) is linearly dependent. Thus, there exist coefficients \(\beta _{1},\beta _{2},\ldots ,\beta _{k}\in F\) that satisfy \(\beta _{1}v_{1}+\beta _{2}v_{2}+\cdots +\beta _{k}v_{k}=\mathbf{0}\) and that are not all zero. Pick the largest \(i\) with \(\beta _{i}\neq 0\). Then \(\beta _{i+1}=\beta _{i+2}=\cdots =\beta _{k}=0\), so \(\beta _{i}v_{i} = -\left( \beta _{1}v_{1}+\beta _{2}v_{2}+\cdots +\beta _{i-1}v_{i-1}\right) \in \operatorname {span}\left( v_{1},v_{2},\ldots ,v_{i-1}\right)\). Since \(\beta _{i}\neq 0\), we obtain \(v_{i}\in \operatorname {span}\left( v_{1},v_{2},\ldots ,v_{i-1}\right) \), contradicting our assumption.

We have \(\left\vert V\right\vert =\left\vert F\right\vert ^{n}\) (since \(V\) is an \(n\)-dimensional \(F\)-vector space).

By Lemma 2.173, a \(k\)-tuple \(\left( v_{1},v_{2},\ldots ,v_{k}\right) \) of vectors in \(V\) is linearly independent if and only if each \(v_i \notin \operatorname {span}(v_1, \ldots , v_{i-1})\).

We construct such a tuple entry by entry:

• First, we choose \(v_{1} \in V\setminus \left\{ \mathbf{0}\right\} \); thus, there are \(\left\vert V\right\vert - 1\) options. Once \(v_{1}\) has been chosen, \(\operatorname {span}\left( v_{1}\right) \) has dimension \(1\) and thus size \(\left\vert F\right\vert ^{1}\).

• Next, we choose \(v_{2} \in V\setminus \operatorname {span}\left( v_{1}\right)\); thus, there are \(\left\vert V\right\vert -\left\vert F\right\vert ^{1}\) options. Once \(v_{2}\) has been chosen, \(\operatorname {span}\left( v_{1},v_{2}\right) \) has dimension \(2\) and thus size \(\left\vert F\right\vert ^{2}\).

• And so on, until the last vector \(v_{k}\) has been chosen.

The total count is \(\prod _{i=0}^{k-1}\left( \left\vert V\right\vert -\left\vert F\right\vert ^{i}\right) =\prod _{i=0}^{k-1}\left( \left\vert F\right\vert ^{n}-\left\vert F\right\vert ^{i}\right)\) (since \(\left\vert V\right\vert =\left\vert F\right\vert ^{n}\)). When \(k {\gt} n\), both sides are \(0\) since there are no linearly independent \(k\)-tuples in an \(n\)-dimensional space.

By the fiber decomposition: \(|A| = \sum _{b \in B} |f^{-1}(b)|\), where each fiber has cardinality \(m\) by assumption. Hence \(|A| = \sum _{b \in B} m = m \cdot |B|\).

If \(k{\gt}n\), then \(\binom {n}{k}_{\left\vert F\right\vert }=0\) (by Proposition 2.141) and \(\left( \text{\# of }k\text{-dimensional vector subspaces of }V\right) =0\) (since the dimension of a subspace of \(V\) is never larger than the dimension of \(V\)). Hence, for the rest of this proof, we WLOG assume that \(k\leq n\).

Define a map

Observation 1: Each \(k\)-dimensional vector subspace of \(V\) has exactly \(\left( \left\vert F\right\vert ^{k}-\left\vert F\right\vert ^{0}\right) \left( \left\vert F\right\vert ^{k}-\left\vert F\right\vert ^{1}\right) \cdots \left( \left\vert F\right\vert ^{k}-\left\vert F\right\vert ^{k-1}\right)\) preimages under \(f\).

Indeed, let \(W\) be a \(k\)-dimensional vector subspace of \(V\). A preimage of \(W\) under \(f\) is a linind \(k\)-tuple of vectors in \(W\) that spans \(W\). Since \(W\) is \(k\)-dimensional, a \(k\)-tuple of vectors in \(W\) spans \(W\) if and only if it is linind. Hence, the number of preimages is the number of linind \(k\)-tuples in \(W\), which equals \(\prod _{i=0}^{k-1}(|F|^k - |F|^i)\) by Lemma 2.174 (applied to \(W\) and \(k\) instead of \(V\) and \(n\)).

By the multijection principle (Lemma 2.175):

(where the right hand side comes from Lemma 2.174). Therefore,

(by Theorem 2.147 (b)).

By strong induction on \(d + k\), using the \(q\)-Pascal recurrence to relate coefficients of \(\binom {n}{k}_q\) and \(\binom {m}{k}_q\) through \(\binom {n-1}{\cdot }_q\) and \(\binom {m-1}{\cdot }_q\) at lower coefficients.

By induction on \(d + k\). The product formula satisfies a recurrence matching the \(q\)-Pascal identity: extracting the last factor \((1 - q^{k+1})^{-1}\) gives \(\prod _{i=1}^{k+1}(1-q^i)^{-1} = \prod _{i=1}^{k}(1-q^i)^{-1} + q^{k+1} \cdot \prod _{i=1}^{k+1}(1-q^i)^{-1}\). Comparing coefficients and applying the inductive hypothesis completes the proof.

The conjugate is constructed using Young diagram transposition. The involution property follows from the fact that transposing twice recovers the original diagram. The interchange of “max part” and “number of parts” follows from the relationship between row lengths and column lengths under transposition.

Young diagram conjugation provides a bijection between these two sets (Lemma 2.179).

The product \(\prod _{i=1}^{k}(1-q^i)^{-1}\) equals the generating function \(\sum _n |\{ \text{partitions of } n \text{ with all parts } \le k\} | \cdot q^n\) by the theorem on the product form of restricted partition generating functions. Applying Lemma 2.180 converts the restricted partition count to the count of partitions with at most \(k\) parts.

For each integer \(n\geq k\), we have

(Here, the first equality holds by Theorem 2.147 (b).) Since \(\lim _{n\to \infty } q^n = 0\) (coefficientwise), for each \(i \in \{ 1,\ldots ,k\} \) we have \(\lim _{n\to \infty }(1-q^{n-k+i}) = 1\). Hence, by Corollary 1.466,

The equality \(\sum _{n\in \mathbb {N}}(p_0(n)+p_1(n)+\cdots +p_k(n))\, q^n = \prod _{i=1}^k \frac{1}{1-q^i}\) follows from Theorem 2.49 (with the letters \(x\), \(m\) and \(k\) renamed as \(q\), \(k\) and \(i\)).

The proof establishes coefficientwise stabilization via Lemma 2.177 (showing that for \(n \ge d + k\), the \(d\)-th coefficient of \(\binom {n}{k}_q\) is constant) and Lemma 2.178 (identifying the stable value with the product formula). The equality with the partition generating function is proved in Theorem 2.181 using Young diagram conjugation to biject partitions with parts \(\le k\) and partitions with \(\le k\) parts.