ON q-DIFFERENCE EQUATIONS FOR PARTITIONS WITHOUT
k-SEQUENCES
KATHRIN BRINGMANN, JEREMY LOVEJOY, AND KARL MAHLBURG
Abstract. In his study of partitions without k-sequences, Andrews proved a double hypergeometric q-series representation of the generating series and a corresponding k-term
q-difference equation. In this note we give new proofs of the double series formula, as well
as a new two-term q-difference equation. In both cases, we provide independent analytic
and combinatorial proofs.

1. Introduction and statement of results
A partition of a positive integer n is a non-increasing sequence of positive integers whose
sum is n, and the number of partitions of n is traditionally denoted by p(n) (a generalreference is [3]). A sequence in a partition is any subsequence of consecutive integers thateach appear as parts. If such a sequence consists of k consecutive integers, it is known asa k-sequence. In particular, any non-empty partition trivially contains a 1-sequence. The
number of partitions that do not contain a k-sequence is denoted by pk (n), and we write thecorresponding generating function asX
Gk (q) :=pk (n)q n .
n≥0Integer partitions without sequences were first studied by MacMahon [11]. In particular,
he used partition conjugation to show that partitions without sequences are equinumerous
with partitions in which all parts are repeated, with the possible exception of the largest
part. This directly gives a hypergeometric q-series expression for the generating function,
namelyXq n (q 6 ; q 6 )n−1,
(1.1)
G2 (q) = 1 +(1 − q n ) (q 2 ; q 2 )n−1 (q 3 ; q 3 )n−1
n≥1
Qn−1
(1 − aq j ).
where the q-Pochhammer symbol is defined by (a)n = (a; q)n := j=0
The family of partitions without k-sequences was introduced in [9], where they were ofinterest because of their relationship to probabilistic bootstrap percolation models. In particular, the metastability threshold of the k-cross neighborhood is intimately related to asymptotic estimates of pk (n); see [6] and [8] for further discussion of these approximations. In [5]the first and the third author considered the case of partitions without sequences and foundan asymptotic series for p2 (n) with polynomial error by amplifying the Hardy-Ramanujan
Circle Method using a Saddle Point analysis. Indeed, this case is of particular interest in
The research of the first author was supported by the Alfried Krupp Prize for Young University Teachersof the Krupp Foundation. The third author was supported by NSF Grant DMS-1201435. The first and third
authors thank the Alexander von Humboldt Foundation.
1

number theory due to an alternative form of (1.1) found by Andrews [2] that involves one ofRamanujan’s mock theta functions as described in [12]. The most recent progress in the analytic study of partitions without k-sequences is due to Kane and Rhoades [10], who proveda refined form of an asymptotic formula conjectured by Andrews [2], by giving the general
asymptotic formula
s 
 
 14
 !
2
1
2
2
1 1
1−
π
1−
n .
(1.2)
pk (n) ∼3 exp
2k 6
k(k + 1)3
k(k + 1)n4
They achieved this by analyzing a Markov-type process for generating partitions without
k-sequences; see [7] for a related setting in which bootstrap percolation models and Markovtype processes arise. This asymptotic analysis is quite different from that used in [4], inwhich the Constant Term Method was used to determine the asymptotic enumeration of
overpartitions with k-sequences. Strikingly, it can be checked that the analogous calculation
fails in the case of partitions without k-sequences, so (1.2) cannot be proven in this way.
In this note we are primarily interested in the combinatorial theory of partitions without ksequences. This aspect is also found in Andrews’ study, as he evaluated all of the generating
functions Gk (q). In particular, Theorem 2 of [2] gives a uniform double q-hypergeometricseries expansion for all k ≥ 1:
(1.3)

Gk (q) =X (−1)r q

1(q; q)∞ r,s≥0(k+1)k(r+s)2+ (k+1)(s+1)s2
2(q k ; q k )r (q k+1 ; q k+1 )s.

Note that this formula includes the case k = 1, where it is clear combinatorially that G1 (q) =1.
Andrews’ proof follows from the the theory of q-difference equations. To describe this,defineX
Gk (x) = Gk (x; q) :=pk (m, n)xm q n ,n,m≥0

where pk (m, n) denotes the number of partitions of n into m parts that contain no ksequences. Andrews showed that
(1.4)

Gk (x) = Gk (xq) +k−1 j j(j+1)
X
x q 2 Gk (xq j+1 )
j=1(xq; q)j,which can be derived as a combinatorial identity by conditioning on the length of the sequencethat begins with the part 1 (the first term corresponds to the case that there is no suchsequence). It is then a standard calculation to verify that
(1.5)

gk (x; q) :=X xkr+(k+1)s (−1)r q1(xq; q)∞ r,s≥0(k+1)k(r+s)2+ (k+1)(s+1)s2
2(q k ; q k )r (q k+1 ; q k+1 )ssatisfies the difference equation (1.4) and the same initial conditions, and is therefore theunique solution (cf. Lemma 1 of [1]). Setting x = 1 then gives (1.3).
In fact, the q-difference equation (1.4) is useful not only for evaluating the generating
function Gk (q) in closed form, but also fundamentally underlies the techniques used in the2asymptotic analysis of pk (n). Indeed, the Markov-type process found in [10] can be understood as the direct conversion of the k-term recurrence into a linear recurrence on ak-dimensional vector space (again, see [7] for a related example).
In light of the importance of the q-difference equation, this note was inspired by theobservation that the double sum in (1.3) and k-term recurrence in (1.4) are counter tothe general philosophy that an `-fold summation should correspond to an `-fold q-difference
equation. Our first main result remedies this, as we give a new two-term q-difference equation
for Gk (x; q).
Theorem 1.1. If |q| < 1, |x| ≤ 1, and k ≥ 1, thenk(k+1)

1
xk q 2Gk (x) =Gk (xq) −1 − xq(xq)kGk xq k+1 .

Remark. Although the coefficients of Gk (x) are non-negative, this is not manifestly evident
from either (1.3) or Theorem 1.1 (in contrast to (1.4)).
We provide two proofs of Theorem 1.1 in Section 2, beginning with an analytic derivationof our new q-difference equation from Andrews’ original recurrence. This is followed by anindependent combinatorial argument using an inclusion-exclusion enumeration of partitions
without k-sequences. The note concludes in Section 3, where we provide two new proofsof the double hypergeometric q-series in (1.3). The first proof is again a direct algebraic
calculation from the q-difference equation. For the second proof we employ an alternative
combinatorial setting. Instead of partitions with without k-sequences, we consider partitions
that can be decomposed into a disjoint collection of k and (k + 1)-sequences, with the further
condition that for each k-sequence, the next largest part does not occur in the partition.
2. Proof of q-difference equation
In this section we prove Theorem 1.1. We first use Andrews’ original proof of (1.3) to derive
the new two-term q-difference equation, but we then give a new combinatorial argument thatis independent from Andrews’ work.
2.1. Analytic argument. The q-difference equation for Gk (x; q) is greatly simplified if one
instead defines(2.1)

Fk (x) = Fk (x; q) := (xq; q)∞ Gk (x; q).

Theorem 1.1 follows immediately from a two-term q-difference equation for Fk (x).
Proposition 2.1. If |q| < 1, |x| ≤ 1, and k ≥ 2, thenFk (x) − Fk (xq) = −xk qk(k+1)2
1 − xq k+1 Fk xq k+1 .

Proof. Multiplying through by (xq)∞ , Andrews’ q-difference equation from (1.4) yields
Fk (x) = (xq)∞ Gk (xq) +

k−1
X

xj q

j(j+1)
2
xq j+1 ∞ Gk xq j+1

j=1= (1 − xq)Fk (xq) +

k−1
X

xj q

j=1

3

j(j+1)2
1 − xq j+1 Fk xq j+1 .

Rearranging terms then gives a convenient q-difference equation for Fk (x), namely
(2.2)

k−1
X

Fk (x) − Fk (xq) = −xqFk (xq) +xj qj(j+1)2
1 − xq j+1 Fk xq j+1 .

j=1

The goal is therefore to show that the right side of this expression collapses to a single term.
For this, we write the expansion in powers of x as
X
Fk (x) =fm (q)xm .
m≥0

Abbreviating fm = fm (q), equation (2.2) then becomesX(1 − q m ) fm xm =m≥0X

−xm+1 q m+1 fm +

k−1
X

!
fm 1 − xqj+1

xm+j qj(j+1)+m(j+1)
2

.

j=1

m≥0
m

Isolating the coefficient of x , we thus have the equality
k−1 

X
j(j+1)
mm+(m−j)(j+1)(m−j−1)(j+1)+ 21 (j+2)(j+1)
2(1 − q ) fm = −q fm−1 +q
fm−j − q
fm−j−1
j=1

(2.3)

= −q

m

1−q

m−1



fm−1 −

k−1
X

q mj−

j(j−1)2k(k−1)
1 − q m−j fm−j − q mk− 2 fm−k .

j=2Note that the first term on the right hand side contains (1 − q m−1 )fm−1 , which can berecursively replaced again using (2.3). After doing so the inner sums cancel, and a bit ofalgebra yields the simple identity(2.4)(1 − q m )fm = q m(k+1)−

k(k+1)
2(fm−k−1 − fm−k ) .

Multiplying (2.4) by xm and summing over m we recover the corresponding series identityX
k(k+1)
k(k+1)Fk (x) − Fk (xq) =−q (m+k)(k+1)− 2 fm xm+k + q (m+k+1)(k+1)− 2 fm xm+k+1
m≥0= −xk qk(k+1)
2

Fk xq k+1


1 − xq k+1 ,which completes the proof.

Proof of Theorem 1.1. Inserting Proposition 2.1 into the definition (2.1) gives
k(k+1)(xq)∞ Gk (x) − (xq 2 )∞ Gk (xq) = −xk q 2
1 − xq k+1 xq k+2 ∞ Gk xq k+1 .
This is equivalent to the q-difference equation in the theorem statement.



2.2. Combinatorics of the difference equation. Although we used Andrews’ q-difference
equation (1.4) at the beginning of our proof in Section 2.1, our new q-difference equationand the double hypergeometric series for Gk (q) can also be proven independently. In thissection we provide a second proof of Theorem 1.1 using combinatorial partition theory; thearguments in the previous section can then be derived in reverse order without appealing toAndrews’ work.
Specifically, we prove Theorem 1.1 directly using an “inclusion-exclusion” type enumeration argument. Referring to the q-difference equation from the theorem statement, the4left-hand side is by definition the two-variable generating function for all partitions without
k-sequences. If all of the 1s in such a partition are removed, the remaining parts still forma partition without k-sequences. The first term on the right-hand side generates all suchpartitions, with an arbitrary number of 1s added to partitions without k-sequences thatbegin with a part of size 2 or larger. But this first term is an overcount, as it also includes
partitions that contain a 1 in addition to the (k − 1)−sequence 2, 3, . . . k. Taken together,
these parts form a k-sequence. The overcount is then corrected by subtracting the second
term on the right, which generates all partitions with the k-sequence 1, 2, . . . , k, no k + 1,
and no other k-sequences.
3. Proof of double summation formula
In this section we provide two new proofs of the double summation formula (1.3). In
the first proof we verify algebraically that the two-variable double series satisfies our new qdifference equation from Theorem 1.1, and for the second proof we give a new combinatorialdescription in terms of a certain weighted enumeration of partitions into distinct parts.
3.1. Analytic verification. Our first proof is similar to that used by Andrews in [2] whenverifying that the double series satisfies (1.4). In particular, our aim is now to show thatfk (x) = fk (x; q) :=X xkr+(k+1)s (−1)r q(k+1)k(r+s)2+ (k+1)(s+1)s2
2(q k ; q k )r (q k+1 ; q k+1 )sr,s≥0

satisfies the q-difference equation from Proposition 2.1. Specifically, we see that
(3.1)

fk (x) − fk (xq) =X xkr+(k+1)s (−1)r qr,s≥0(k+1)k(r+s)2+ (k+1)(s+1)s
2
2(q k ; q k )r (q k+1 ; q k+1 )s
1 − q kr+(k+1)s .

Rewriting1 − q kr+(k+1)s = 1 − q (k+1)s + q (k+1)s 1 − q krand making the appropriate shifts in the summation indices, the right hand side of (3.1)
simplifies to the desired expression
k(k+1)−xk q 2
1 − xq k+1 fk xq k+1(see the proof of Theorem 2.3 in [4] for a similar calculation).
3.2. Combinatorial derivation of double sum. We close by giving a new proof of the
double series representation of Fk (x) in which we use partition combinatorics to analyze
Proposition 2.1. We first rewrite the q-difference equation ask(k+1)
1 − xq k+1 Fk xq k+1 .
(3.2)
Fk (x) = Fk (xq) − xk q 2
This can now be related to the generating function of certain partitions into distinct parts.
In particular, let Pk denote the set of partitions that can be decomposed into a disjointcollection of k and (k + 1)-sequences, with the further condition that for each k-sequence,
the next largest part does not occur in the partition. It is also convenient to refine these sets
by writing Pk (n) for the partitions of n in Pk .
5

Such a partition λ is bijectively associated to a subsequence of natural numbers (a1 , a2 , . . . , aj )withai+1 − ai ≥ k + 1
and each ai being marked as Type k or k + 1 depending on whether it is a k or k + 1-sequencethat begins at ai . The weight of the partition is then defined as w(λ) := #{i | ai is Type k},
and we also denote the number of parts by `(λ) and its size by |λ|. Note that `(λ) =j(k + 1) − w(λ).
For example, if k = 1, the following partition is in P1 (77):(3.3)

λ = 2 + 3 + 4 + 6 + 7 + 8 + 9 + 11 + 13 + 14.

The associated subsequence is (a1 , a2 , a3 , a4 , a5 , a6 ) = (2, 4, 6, 8, 11, 13), with corresponding
Types (2, 1, 2, 2, 1, 2); its weight is w(λ) = 2 and its length is `(λ) = 10.
With these definitions, (3.2) can now be understood as a combinatorial statement aboutsuch partitions.
Lemma 3.1. Suppose that k ≥ 1 and Fk (x; q) is a double series that satisfies (3.2) andFk (0; 0) = 1. Then it can be expanded asXFk (x) = Fk (x; q) =Qk (m, n)xm q n ,
m,n≥0

where
Qk (m, n) :=X(−1)w(λ) .

λ∈Pk (n)`(λ)=m

Proof. Following (3.2), we see that a non-zero term in Fk (x) is constructed by choosing
k(k+1)(k+1)(k+2)
2either −xk q 2 Fk (xq k+1 ) or xk+1 q
Fk (xq k+1 ). The first case corresponds to a Typek sequence beginning at 1; note that the exponents on x and q count the parts 1, 2, . . . k,that there is a weight of −1, and that if (3.2) is iteratively applied to Fk (xq k+1 ), the next
part is at least k + 2. The second case analogously corresponds to a Type k + 1 sequence
beginning at 1, which completes the proof.
A further combinatorial analysis of Lemma 3.1 gives another, independent proof of thehypergeometric series representation of Fk (x). Our combinatorial argument is illustrated bya simple example following the proof.
Proposition 3.2. If |q| < 1, |x| ≤ 1, and k ≥ 2, thenFk (x) =X xkr+(k+1)s (−1)r qr,s≥0(k+1)k(r+s)2+ (k+1)(s+1)s2
2(q k ; q k )r (q k+1 ; q k+1 )s.

Proof. Suppose that λ ∈ Pk (n) and `(λ) = m. Since this is a partition into distinct parts,
if we remove the triangular partition 1 + 2 + · · · + m, then we are left with a new partition
λ0 . We thus obtain a new subsequence (a01 , . . . , a0m ) such that 0 ≤ a01 and a0i ≤ a0i+1 , withstrict inequality if ai is Type k. Furthermore, each k or (k + 1)-sequence in λ becomes,
respectively, a grouping of k or k + 1 identical parts in λ0 .
Taken together, this means that λ0 decomposes into a partition into distinct multiples ofk and an ordinary partition into multiples of k + 1 (where parts of size 0 are allowed). The
6

q-binomial theorem (see Corollary 2.2 in [1]) then gives a double series for the generating
functionk k
XX (−1)r xkr+(k+1)s q kr(r−1)
2
x
;
q
0
w(λ) `(λ) |λ |
∞
(3.4)
(−1)
x q = k+1 k+1
=
.
k
k
k+1
k+1
(x
;
q
)
(q
;
q
)
(q
;
q
)
∞
r
s
r,s≥0
λ∈P
k

Note that in the double series, each λ is associated to a pair (r, s), where r is the number of
ai of Type k, s is the number of ai of Type k + 1, and `(λ) = kr + (k + 1)s.
To complete the proof, observe that|λ| = |λ0 | +`(λ)(`(λ) + 1).
2

Recalling Lemma 3.1 and plugging in to (3.4), we obtain
Fk (x) =(kr+(k+1)s)(kr+(k+1)s+1)+
X (−1)r xkr+(k+1)s q kr(r−1)
2
2

r,s≥0

(q k ; q k )r (q k+1 ; q k+1 )s

Simplifying the exponent gives the proposition statement.

.


Remark. For the example from (3.3), the associated λ0 is 1 + 1 + 1 + 2 + 2 + 2 + 2 + 3 + 4 + 4,
which decomposes into the partition into distinct parts 1 + 3 and the partition into evenparts 2 + 4 + 4 + 8.
Remark. Similar to the discussion of (1.5), the solution to (3.2) is unique subject to theassumption that the series Fk (x) begins with 1.
References[1] G. Andrews, On q-difference equations for certain well-poised basic hypergeometric series, Quart. J.
Math. 19 (1968), 433–447.
[2] G. Andrews, Partitions with short sequences and mock theta functions, Proc. Natl. Acad. Sci. 102(2005), 4666–4671.
[3] G. Andrews, The theory of partitions, Cambridge University Press, Cambridge, 1998.
[4] K. Bringmann, A. Holroyd, K. Mahlburg, and M. Vlasenko, k-run overpartitions and mock theta functions, to appear in Q. J. Math.
[5] K. Bringmann and K. Mahlburg, An extension of the Hardy-Ramanujan circle method and applications
to partitions without sequences, Amer. J. Math. 133 (2011), 1151–1178.
[6] K. Bringmann and K. Mahlburg, Improved bounds on metastability thresholds and probabilities forgeneralized bootstrap percolation, Trans. Am. Math. Soc. 364 (2012), 3829–3859.
[7] K. Bringmann, K. Mahlburg, and A. Mellit, Convolution bootstrap percolation models, Markov-type
stochastic processes, and mock theta functions, Int. Math. Res. Not. (2013), 971–1013[8] J. Gravner, A. Holroyd and R. Morris, A sharper threshold for bootstrap percolation in two dimensions,Prob. Th. Rel. Fields 153 (2012), 1–23.
[9] A. Holroyd, T. Liggett, and D. Romik, Integrals, partitions, and cellular automata, Trans. Am. Math.
Soc. 356 (2004), 3349–3368.
[10] D. Kane and R. Rhoades, A proof of Andrews’s conjecture and partitions with no short sequences,preprint.
[11] P. MacMahon, Combinatory Analysis Vol. II, Cambridge Univ. Press, Cambridge, 1916, 49–58.
[12] G. Watson, The final problem: An account of the mock theta functions, J. London Math. Soc. 11 (1936),
55–80.
7

Mathematical Institute, University of Cologne, Weyertal 86-90, 50931 Cologne, Germany
E-mail address: kbringma@math.uni-koeln.de
CNRS, LIAFA, Universite Denis Diderot - Paris 7, 75205 Paris Cedex 13, FRANCE
E-mail address: lovejoy@liafa.univ-paris-diderot.fr
Department of Mathematics, Louisiana State University, Baton Rouge, LA 70802, U.S.A.
E-mail address: mahlburg@math.lsu.edu

8