New Partition Function Recurrences

Robson da Silva^{1} and Pedro Diniz Sakai Departamento de Ciência e Tecnologia Universidade Federal de São Paulo São José dos Campos, SP, 12247–014 Brazil

                    silva.robson@unifesp.br
                    pedro.sakai@unifesp.br

Abstract We present Euler-type recurrence relations for some partition functions. Some of our results provide new recurrences for p(n) the number of unrestricted partitions of n. Others establish recurrences for partition functions not yet considered.

1 Introduction

A partition of an integer n is a finite set of positive integers {λ_{1}, …, λ_{s}} such that n = λ_{1} + ⋯ + λ_{s}. The λ_{i} are called the parts of the partition. The number of partitions of n is usually denoted by p(n) [9, \underline{A000041}], with p(0) = 1 by convention. For example, we have p(4) = 5 since there are five partitions of 4, namely

4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

The generating function of p(n), due to Euler [1, Eq. (1.1.6)], is given by

∑_{n=0}^{∞} p(n)q^{n} = ∏_{k=1}^{∞} \frac{1}{1 − q^{k}} .  (1)

1Corresponding author.

So, one can obtain the values of p(n) by expanding the right-hand side of (1) and extracting the coefficient of q^{n}. Another way to obtain p(n) was found by Euler after he proved the following identity (known as Euler’s pentagonal number theorem):

∑_{n=−∞}^{∞}(−1)^{n}q^{n(3n−1)/2} = ∏_{k=1}^{∞}(1 − q^{k}).  (2)

Indeed, multiplying (1) and (2) we obtain

∑_{n=0}^{∞} p(n)q^{n} ∑_{n=−∞}^{∞}(−1)^{n}q^{n(3n−1)/2} = 1,

from which the following recurrence for p(n) is derived after extracting the coefficient of q^{n} from both sides:

p(n) − p(n − 1) − p(n − 2) + p(n − 5) + p(n − 7) − p(n − 12) − p(n − 15)
+ ⋯ + (−1)^{j}p(n − j(3j − 1)/2) + (−1)^{j}p(n − j(3j + 1)/2) + ⋯
= \begin{cases}1, & if n = 0; \\ 0, & otherwise. \end{cases}

The numbers j(3j ± 1)/2 are the pentagonal numbers [9, \underline{A001318}].

Some subsequent works brought new recurrence relations for p(n) and other partition functions. Ewell [4, Theorem 2], for instance, presented the following recurrence for p(n) involving the triangular numbers [9, \underline{A000217}]

p(n) − p(n − 1) − p(n − 3) + p(n − 6) + p(n − 10) − p(n − 15) − p(n − 21)
+ ⋯ + (−1)^{j}p(n − j(2j − 1)) + (−1)^{j}p(n − j(2j + 1)) + ⋯
= \begin{cases}0, & if n is odd; \\ p_{d}(n/2), & if n is even, \end{cases}

where p_{d}(n) denotes the number of partitions of n into distinct parts [9, \underline{A000009}]. Merca [6] derived two new recurrence relations for p(n), which allowed him to obtain a more efficient method to compute the parity of p(n). Ono, Robbins, and Wilson [8] presented recurrence relations for some partition functions, including p_{d}(n), qq(n) (the number of partitions into distinct odd parts [9, \underline{A000700}]), p_{E}(n) (the number of partitions into an even number of parts [9, \underline{A027187}]), and p_{O}(n) (the number of partitions into an odd number of parts [9, \underline{A027193}]). Recently, Choliy, Kolitsch, and Sills [2] found a number of new recurrences for p(n), including

p(n) − p(n − 1) − p(n − 2) + p(n − 4) + p(n − 8) − p(n − 9) − p(n − 18)
+ ⋯ + (−1)^{j}p(n − j^{2}) + (−1)^{j}p(n − 2j^{2}) + ⋯
= \begin{cases}0, & if n is odd; \\ qq(n), & if n is even, \end{cases}

and

p(n) − 2p(n − 1) + 2p(n − 4) − 2p(n − 9) + 2p(n − 16) + ⋯
+(−1)^{j}2p(n − j^{2}) + ⋯ = (−1)^{n}qq(n).

Additional recurrence relations for partition functions can be found in [2, 4, 5, 6, 7, 8].

In this paper, using some classical identities and generating function manipulations, we provide a number of new recurrence relations for p(n), qq(n), \overline{p}(n) the number of overpartitions of n [9, \underline{A015128}], p_{o}(n) the number of partitions of n into odd parts [9, \underline{A000009}], and the two-parameter function p_{m}^{c}(n) (the number of partitions of n into parts congruent to ±c modulo m). For some of these functions, it is the first time that recurrence relations are presented.

2 Preliminaries

We recall Ramanujan’s theta functions

f(a, b) := ∑_{n=−∞}^{∞} a^{\frac{n(n+1)}{2}} b^{\frac{n(n−1)}{2}} , for |ab| < 1,  (3)

and

ψ(q) := f(q, q^{3}) = ∑_{n=0}^{∞} q^{n(n+1)/2}.  (4)

In the proofs of some of our results, we will need Jacobi triple product identity [1, Theorem 1.3.3] given by

∑_{n=−∞}^{∞} z^{n}q^{n^{2}} = (−zq; q^{2})_{∞}(−q/z; q^{2})_{∞}(q^{2}; q^{2})_{∞},

where we use the following standard q-series notation:

(a; q)_{0} = 1,
(a; q)_{n} = (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}), ∀n ≥ 1,

and

(a; q)_{∞} = lim_{n→∞}(a; q)_{n}, |q| < 1.

Using (3), we can rewrite Jacobi triple product identity in the form

f(a, b) = (−a; ab)_{∞}(−b; ab)_{∞}(ab; ab)_{∞}.  (5)

An important consequence of (5) is following identity (see [1, Eq. (1.3.14)])

ψ(q) = \frac{(q^{2}; q^{2})_{∞}}{(q; q^{2})_{∞}} .  (6)

We also recall the well-known Euler’s pentagonal number theorem [1, Corollary 1.3.5]:

(q; q)_{∞} = ∑_{n=−∞}^{∞}(−1)^{n}q^{n(3n−1)/2}.  (7)

3 Main results

In what follows, we let t_{j}^{e} (resp., t_{j}^{o}) denote the j-th even (resp., odd) triangular number [9, \underline{A014494}] (resp., [9, \underline{A014493}]). So, t_{1}^{e} = 0, t_{1}^{o} = 1, t_{2}^{e} = 6, t_{2}^{o} = 3, t_{3}^{e} = 10, t_{3}^{o} = 15, etc.

Theorem 1. For all even integer n ≥ 0, we have

p(n/2) + p((n − 6)/2) + p((n − 10)/2) + p((n − 28)/2) + p((n − 36)/2)+
p((n − 66)/2) + p((n − 78)/2) + ⋯ + p((n − t_{j}^{e})/2) + ⋯ = p_{d}(n),  (8)

where p_{d}(n) denotes the number of partitions of n into distinct parts. For all odd integer n ≥ 0, we have

p((n − 1)/2) + p((n − 3)/2) + p((n − 15)/2) + p((n − 21)/2)+
p((n − 45)/2) + p((n − 55)/2) + ⋯ + p((n − t_{j}^{o})/2) + ⋯ = p_{o}(n),  (9)

where p_{o}(n) = p_{d}(n) denotes the number of partitions of n into odd parts

Proof. Initially, we note that

∑_{n=0}^{∞} \frac{1 + (−1)^{n}}{2} p_{d}(n)q^{n} = \frac{1}{2}( ∑_{n=0}^{∞} p_{d}(n)q^{n} + ∑_{n=0}^{∞} p_{d}(n)(−q)^{n})

= \frac{1}{2}( ∏_{k=1}^{∞}(1 + q^{k}) + ∏_{k=1}^{∞}(1 + (−1)^{k}q^{k}))

= \frac{1}{2}( ∏_{k=1}^{∞}(1 + q^{k}) + ∏_{k=1}^{∞}(1 + q^{2k})(1 − q^{2k−1}))

and

∏_{k=1}^{∞}(1 + q^{k}) = ∏_{k=1}^{∞}(1 + q^{k})\frac{(1 − q^{k})}{(1 − q^{k})} \frac{(1 − q^{2k−1})}{(1 − q^{2k−1})}

= ∏_{k=1}^{∞} \frac{(1 − q^{2k−1})(1 − q^{2k})}{(1 − q^{k})(1 − q^{2k−1})} = ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(q).

We also have

∏_{k=1}^{∞}(1 + q^{2k})(1 − q^{2k−1}) = ∏_{k=1}^{∞}(1 + q^{2k})(1 − q^{2k−1})\frac{(1 − q^{2k})}{(1 − q^{k})(1 + q^{k})}

= ∏_{k=1}^{∞} \frac{(1 − q^{2k−1})(1 − q^{2k})}{(1 − q^{k})(1 + q^{2k−1})} = ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(−q).

It follows that

∑_{n=0}^{∞} \frac{1 + (−1)^{n}}{2} p_{d}(n)q^{n} = \frac{1}{2}( ∏_{k≥1} \frac{1}{1 − q^{2k}} ψ(q) + ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(−q))

= ( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} )\frac{1}{2}(ψ(q) + ψ(−q))

= ( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} )\frac{1}{2}( ∑_{j=0}^{∞} q^{\frac{j(j+1)}{2}} + ∑_{j=0}^{∞}(−q)^{\frac{j(j+1)}{2}} ).

The parity of the exponent \frac{j(j+1)}{2} is given by

\frac{4i(4i + 1)}{2} = 8i^{2} + 2i,  (10)
\frac{(4i − 1)(4i − 1 + 1)}{2} = 8i^{2} − 2i,  (11)
\frac{(4i − 2)(4i − 2 + 1)}{2} = 8i^{2} − 6i + 1,  (12)
\frac{(4i − 3)(4i − 3 + 1)}{2} = 8i^{2} − 10i + 3.  (13)

The even triangular numbers are given by (10) and (11), while (12) and (13) represent the odd triangular numbers. Thus

∑_{j=0}^{∞} q^{\frac{j(j+1)}{2}} = ∑_{i=0}^{∞} q^{8i^{2}+2i} + q^{8i^{2}−2i} + q^{8i^{2}−6i+1} + q^{8i^{2}−10i+3}  (14)

and

∑_{j=0}^{∞}(−q)^{\frac{j(j+1)}{2}} = ∑_{i=0}^{∞} q^{8i^{2}+2i} + q^{8i^{2}−2i} − q^{8i^{2}−6i+1} − q^{8i^{2}−10i+3},  (15)

which yields

∑_{n=0}^{∞} \frac{1 + (−1)^{n}}{2} p_{d}(n)q^{n} = ( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} )\frac{1}{2} ∑_{i=0}^{∞} 2q^{8i^{2}+2i} + 2q^{8i^{2}−2i}

= ∑_{k=0}^{∞} p(k)q^{2k} ∑_{j=0}^{∞} q^{t_{j}^{e}} = ∑_{k=0}^{∞} ∑_{j=0}^{∞} p(k)q^{2k+t_{j}^{e}}.

Now we extract the coefficient of q^{n} on both sides of the above equation to obtain

∑_{n=0}^{∞} p_{d}(n)q^{n} = ∑_{n=0}^{∞} ( ∑_{j=0}^{∞} p((n − t_{j}^{e})/2))q^{n},

which completes the proof of (8).

In order to prove (9), we begin with

∑_{n=0}^{∞} \frac{1 − (−1)^{n}}{2} p_{o}(n)q^{n} = \frac{1}{2}( ∑_{n=0}^{∞} p_{o}(n)q^{n} − ∑_{n=0}^{∞} p_{o}(n)(−q)^{n})

= \frac{1}{2}( ∏_{k=1}^{∞} \frac{1}{(1 − q^{2k−1})} − ∏_{k=1}^{∞} \frac{1}{(1 − (−q)^{2k−1})})

= \frac{1}{2}( ∏_{k=1}^{∞} \frac{1}{(1 − q^{2k−1})} − ∏_{k=1}^{∞} \frac{1}{(1 + q^{2k−1})}).

We note that

∏_{k=1}^{∞} \frac{1}{(1 − q^{2k−1})} = ∏_{k=1}^{∞} \frac{1}{(1 − q^{2k−1})} \frac{(1 − q^{2k})}{(1 − q^{2k})} = ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(q)

and

∏_{k=1}^{∞} \frac{1}{(1 + q^{2k−1})} = ∏_{k=1}^{∞} \frac{1}{(1 + q^{2k−1})} \frac{(1 − q^{2k})}{(1 − q^{2k})} = ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(−q).

It follows that

∑_{n=0}^{∞} \frac{1 − (−1)^{n}}{2} p_{o}(n)q^{n} = \frac{1}{2}( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(q) − ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} ψ(−q))

= ( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} )\frac{1}{2}(ψ(q) − ψ(−q))

= ( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} )\frac{1}{2}( ∑_{j=0}^{∞} q^{\frac{j(j+1)}{2}} − ∑_{j=0}^{∞}(−q)^{\frac{j(j+1)}{2}} ).

By (14) and (15), we have

∑_{n=0}^{∞} \frac{1 − (−1)^{n}}{2} p_{o}(n)q^{n} = ( ∏_{k=1}^{∞} \frac{1}{1 − q^{2k}} )\frac{1}{2}( ∑_{i=0}^{∞} 2q^{8i^{2}−6i+1} + 2q^{8i^{2}−10i+3})

= ∑_{k=0}^{∞} p(k)q^{2k} ∑_{j=0}^{∞} q^{t_{j}^{o}} = ∑_{k=0}^{∞} ∑_{j=0}^{∞} p(k)q^{2k+t_{j}^{o}}.

Extracting the coefficient of q^{n} in the identity above, we obtain

∑_{n=0}^{∞} p_{o}(n)q^{n} = ∑_{n=0}^{∞} ( ∑_{j=0}^{∞} p((n − t_{j}^{o})/2))q^{n},

from which (9) follows.

We recall that Corteel and Lovejoy [3] introduced the overpartitions of n, which are partitions in which the first occurrence of a number may be overlined. For instance, there are eight overpartitions of 3, namely

3, \overline{3}, 2 + 1, \overline{2} + 1, 2 + \overline{1}, \overline{2} + \overline{1}, 1 + 1 + 1, \overline{1} + 1 + 1.

We let \overline{p}(n) denote the number of overpartitions of n [9, \underline{A015128}]. In the next three results, we present recurrence relations for \overline{p}(n).

Theorem 2. For all n ≥ 0, we have

\overline{p}(n) − 2\overline{p}(n − 1) + 2\overline{p}(n − 4) − 2\overline{p}(n − 9) + 2\overline{p}(n − 16) − 2\overline{p}(n − 25)+
2\overline{p}(n − 36) − ⋯ + 2(−1)^{j}\overline{p}(n − j^{2}) + ⋯
= \begin{cases}1, & if n = 0; \\ 0, & otherwise. \end{cases}

Proof. We recall from [3] that the generating function for overpartitions is given by

∑_{n=0}^{∞} \overline{p}(n)q^{n} = ∏_{k=1}^{∞} \frac{(1 + q^{k})}{(1 − q^{k})}.

We note that

∏_{k=1}^{∞}(1 − q^{k}) = ∏_{k=1}^{∞}(1 − q^{k})\frac{(1 − q^{2k−1})}{(1 − q^{2k−1})} \frac{(1 − q^{2k})}{(1 − q^{2k})}

= ∏_{k=1}^{∞} \frac{(1 − q^{k})(1 − q^{2k−1})(1 − q^{2k})}{(1 − q^{2k})(1 − q^{2k−1})}

= ∏_{k=1}^{∞} \frac{(1 − q^{2k−1})^{2}(1 − q^{2k})}{(1 − q^{2k−1})}

= φ(−q) ∏_{k=1}^{∞} \frac{1}{(1 − q^{2k−1})}.

By Euler’s identity, we have

∏_{k=1}^{∞}(1 − q^{k}) = φ(−q) ∏_{k=1}^{∞}(1 + q^{k}),

and, then,

∏_{k=1}^{∞} \frac{1}{(1 − q^{k})} = \frac{1}{φ(−q)} ∏_{k=1}^{∞} \frac{1}{(1 + q^{k})}.

Hence we obtain the following equivalent identities:

∑_{n=0}^{∞} \overline{p}(n)q^{n} = \frac{∏_{k=1}^{∞}(1 + q^{k})}{φ(−q) ∏_{k=1}^{∞}(1 + q^{k})},
φ(−q) ∑_{n=0}^{∞} \overline{p}(n)q^{n} = 1,
(1 + 2 ∑_{k=1}^{∞}(−1)^{k}q^{k^{2}}) ∑_{n=0}^{∞} \overline{p}(n)q^{n} = 1,
∑_{n=0}^{∞} (\overline{p}(n)q^{n} + 2 ∑_{k=1}^{∞}(−1)^{k}\overline{p}(n)q^{k^{2}+n}) = 1,
∑_{n=0}^{∞} (\overline{p}(n) + 2 ∑_{k=1}^{∞}(−1)^{k}\overline{p}(n − k^{2}))q^{n} = 1.

The result now follows from the last identity.

Our second recurrence for \overline{p}(n) involves p_{d}(n). Theorem 3. For all n ≥ 0, we have

\overline{p}(n) − \overline{p}(n − 1) − \overline{p}(n − 2) + \overline{p}(n − 5) + \overline{p}(n − 7) − ⋯

⋯ + (−1)^{j} (\overline{p}(n − j(3j − 1)/2) + \overline{p}(n − j(3j + 1)/2)) + ⋯ = p_{d}(n).

Proof. We have

∏_{k=1}^{∞}(1 + q^{k}) = ∏_{k=1}^{∞} \frac{(1 + q^{k})}{(1 − q^{k})} ∏_{k=1}^{∞}(1 − q^{k})

= ∑_{k=1}^{∞} \overline{p}(k)q^{k} ∑_{k=−∞}^{∞}(−1)^{j}q^{\frac{j(3j−1)}{2}}

= ∑_{k=0}^{∞} \overline{p}(k)q^{k}(1 + ∑_{j=1}^{∞}(−1)^{j}q^{\frac{j(3j−1)}{2}} + ∑_{j=1}^{∞}(−1)^{j}q^{\frac{j(3j+1)}{2}} )

= ∑_{k=0}^{∞} (\overline{p}(k)q^{k} + ∑_{j=1}^{∞}(−1)^{j}\overline{p}(k)q^{k+ \frac{j(3j−1)}{2}} + ∑_{j=1}^{∞}(−1)^{j}\overline{p}(k)q^{k+ \frac{j(3j+1)}{2}} ).

Therefore, we obtain

∑_{n=0}^{∞}p_{d}(n)q^{n} = ∑_{n=0}^{∞} (\overline{p}(n) + ∑_{j=1}^{∞}(−1)^{j} (\overline{p}(n − j(3j − 1)/2) + \overline{p}(n − j(3j + 1)/2)) )q^{n},

from which the proof follows by comparing coefficients of q^{n} on both sides of the last equation.

We let \overline{p_{d}}(n) denote the number of overpartitions of n into distinct parts. Then we have the following recurrence for \overline{p}(n). Theorem 4. For all n ≥ 0, we have

\overline{p}(n)−\overline{p}(n − 2) − \overline{p}(n − 4) + \overline{p}(n − 10) + \overline{p}(n − 14) − ⋯
⋯ + (−1)^{j}(\overline{p}(n − j(3j − 1)) + \overline{p}(n − j(3j + 1))) + ⋯ = \overline{p_{d}}(n).

Proof. By (7) we have

∑_{k=0}^{∞} \overline{p_{d}}(n)q^{n} = ∏_{k=1}^{∞}(1 + q^{k})^{2} = ∏_{k=1}^{∞} \frac{(1 − q^{2k})(1 + q^{k})}{1 − q^{k}}

= (q^{2}; q^{2})_{∞} ∑_{k=0}^{∞} \overline{p}(k)q^{k} = ∑_{k=0}^{∞} \overline{p}(k)q^{k} ∑_{j=−∞}^{∞}(−1)^{j}q^{j(3j−1)}

= ∑_{k=0}^{∞} \overline{p}(k)q^{k}(1 + ∑_{j=1}^{∞}(−1)^{j}q^{j(3j−1)} + ∑_{j=1}^{∞}(−1)^{j}q^{j(3j+1)})

= ∑_{n=0}^{∞} (\overline{p}(n) + ∑_{j=1}^{∞}(−1)^{j}(\overline{p}(n − j(3j − 1)) + \overline{p}(n − j(3j + 1))))q^{n}.

Thus, the result follows from extracting the coefficient of q^{n} on both sides of this identity.

Now we prove a recurrence relations satisfied by qq(n), the number of partitions of n into distinct odd parts.

Theorem 5. For all n ≥ 0, we have

qq(n) − qq(n − 4) − qq(n − 8) + qq(n − 20) + qq(n − 28) − qq(n − 48)− qq(n − 60) + ⋯ + (−1)^{j}(qq(n − 2j(3j − 1)) + qq(n − 2j(3j + 1))) ⋯

= \begin{cases}1, & if n is a triangular number; \\ 0, & otherwise. \end{cases}

Proof. It is easy to see that

∏_{k=1}^{∞}(1 + q^{2k−1}) = ∏_{k=1}^{∞} \frac{(1 + q^{k})}{(1 + q^{2k})} = ∏_{k=1}^{∞} \frac{(1 + q^{k})(1 − q^{2k})}{(1 − q^{4k})}.

Thus

∑_{j=0}^{∞} qq(j)q^{j} = ∏_{k=1}^{∞} \frac{(1 + q^{k})(1 − q^{2k})}{(1 − q^{4k})},

which can be rewritten as

∏_{k=1}^{∞}(1 − q^{4k}) ∑_{j=0}^{∞} qq(j)q^{j} = ∑_{i=0}^{∞} p_{d}(i)q^{i} ∏_{k=1}^{∞}(1 − q^{2k}).

That is to say

(q^{4}; q^{4})_{∞} ∑_{j=0}^{∞} qq(j)q^{j} = (q^{2}; q^{2})_{∞} ∑_{i=0}^{∞} p_{d}(i)q^{i}.

Then, by (7), we have

(q^{4}; q^{4})_{∞} ∑_{j=0}^{∞} qq(j)q^{j}

= (1 + ∑_{k=1}^{∞}(−1)^{k}q^{2j(3j−1)} + ∑_{k=1}^{∞}(−1)^{k}q^{2j(3j+1)}) ∑_{j=0}^{∞} qq(j)q^{j}

= ∑_{n=0}^{∞} (qq(n) + ∑_{k=0}^{∞}(−1)^{k}(qq(n − 2j(3j − 1)) + qq(n − 2j(3j + 1))))q^{n}.

On the other hand, we have

(q^{2}; q^{2})_{∞} ∑_{i=0}^{∞} p_{d}(i)q^{i}

= ∑_{i=0}^{∞} p_{d}(i)q^{i}(1 + ∑_{k=1}^{∞}(−1)^{k}q^{k(3k−1)} + ∑_{k=1}^{∞}(−1)^{k}q^{k(3k+1)})

= ∑_{n=0}^{∞} (p_{d}(n) + ∑_{k=1}^{∞}(−1)^{k}(p_{d}(n − k(3k − 1)) + p_{d}(n − k(3k + 1))))q^{n}.

Hence

∑_{n=0}^{∞} (qq(n) + ∑_{k=1}^{∞}(−1)^{k}(qq(n − 2j(3j − 1)) + qq(n − 2j(3j + 1))))q^{n}

= ∑_{n=0}^{∞} (p_{d}(n) + ∑_{k=1}^{∞}(−1)^{k}(p_{d}(n − k(3k − 1)) + p_{d}(n − k(3k + 1))))q^{n}.

The result follows from extracting the coefficient of q^{n} on both sides of the last equation and using Theorem 1 of [8].

We let p_{o}(n) denote the number of partitions into odd parts. The next theorem presents a recurrence for p_{o}(n).

Theorem 6. For all n ≥ 0, we have

p_{o}(n)−p_{o}(n − 1) − p_{o}(n − 5) + p_{o}(n − 8) + p_{o}(n − 16) − ⋯
⋯ +(−1)^{j}(p_{o}(n − j(3j − 2)) + p_{o}(n − j(3j + 2))) + ⋯
= \begin{cases}1, & if n is 3 times a triangular number; \\ 0, & otherwise. \end{cases}

Proof. Setting a = −q and b = −q^{5} in (3) and (5) we obtain

(q; q^{6})_{∞}(q^{5}; q^{6})_{∞}(q^{6}; q^{6})_{∞} = f(−q, −q^{5}) = ∑_{j=−∞}^{∞}(−q)^{\frac{j(j+1)}{2}} (−q^{5})^{\frac{j(j−1)}{2}} ,

from which it follows that

∑_{j=−∞}^{∞}(−1)^{j}q^{j(3j−2)} = ∏_{k=1}^{∞}(1 − q^{6k−5})(1 − q^{6k−1})(1 − q^{6k})  (16)

= ∏_{k=1}^{∞}(1 − q^{6k−5})(1 − q^{6k−1})(1 − q^{6k})\frac{(1 − q^{6k−3})}{(1 − q^{6k−3})}

= ∏_{k=1}^{∞} \frac{(1 − q^{2k−1})(1 − q^{6k})}{(1 − q^{6k−3})}.

Then, by (4), we have

ψ(q^{3}) = ∏_{k=1}^{∞} \frac{1}{(1 − q^{2k−1})} ∑_{j=−∞}^{∞}(−1)^{j}q^{j(3j−2)}

= ∑_{i=0}^{∞} p_{o}(i)q^{i}(1 + ∑_{j=1}^{∞}(−1)^{j}q^{j(3j−2)} + ∑_{j=1}^{∞}(−1)^{j}q^{j(3j+2)})

= ∑_{n=0}^{∞} (p_{o}(n) + ∑_{j=1}^{∞}(−1)^{j} (p_{o}(n − j(3j − 2)) + p_{o}(n − j(3j + 2))) )q^{n}.

The result follows by comparing the coefficients of q^{n} on both sides of the last expression.

Let ℓ be a positive integer. A partition of n having no part divisible by ℓ is called an ℓ-regular partition of n. We let b_{ℓ}(n) denote the number of ℓ-regular partitions of n. The generating function of b_{ℓ}(n) is

∑_{n=0}^{∞} b_{ℓ}(n)q^{n} = \frac{(q^{ℓ}; q^{ℓ})_{∞}}{(q; q)_{∞}} .

Our next result is a recurrence relation for p(n) involving b_{ℓ}(n).

Theorem 7. Let ℓ ≥ 1. For all n ≥ 0, we have

p(n) − p(n − ℓ) − p(n − 2ℓ) + p(n − 5ℓ) + p(n − 7ℓ) − ⋯
⋯ + (−1)^{j}(p(n − ℓj(3j − 1)/2) + p(n − ℓj(3j + 1)/2)) + ⋯ = b_{ℓ}(n).

Proof. We have

∑_{n=0}^{∞} b_{ℓ}(n)q^{n}

= ∏_{k=1}^{∞} \frac{(1 − q^{ℓk})}{(1 − q^{k})}

= ∑_{n=0}^{∞} p(n)q^{n}( ∑_{j=−∞}^{∞}(−1)^{j}q^{ℓ \frac{j(3j−1)}{2}} )

= ∑_{n=0}^{∞} p(n)q^{n}(1 + ∑_{j=1}^{∞}(−1)^{j}q^{ℓ \frac{j(3j−1)}{2}} + ∑_{j=1}^{∞}(−1)^{j}q^{ℓ \frac{j(3j+1)}{2}} )

= ∑_{n=0}^{∞} (p(n) + ∑_{j=1}^{∞}(−1)^{j}(p(n)(n − ℓj(3j − 1)/2) + p(n − ℓj(3j + 1)/2))))q^{n},

from which the result follows.

We close this section with a recurrence relation for the number of partitions of n having parts congruent to ±c (mod m).

Theorem 8. Given integers a and m ≥ 1, we let p_{m}^{c}(n) denote the number of partitions of n having parts congruent to ±c modulo m. Then, for all n ≥ 0,

p_{m}^{c}(n)−p_{m}^{c}(n − (m − c)) − p_{m}^{c}(n − c) + p_{m}^{c}(n − (3m − 2c))

+ p_{m}^{c}(n − (m + 2c)) + ⋯ + (−1)^{j}p_{m}^{c}(n − (mj^{2} + (m − 2c)j)/2) + (−1)^{j}p_{m}^{c}(n − (mj^{2} − (m − 2c)j)/2) + ⋯

= \begin{cases}1, & if n = mk_{j}^{e}; \\ −1, & if n = mk_{j}^{o}; \\ 0, & otherwise, \end{cases}

where k_{j}^{e} (resp., k_{j}^{o}) is the j-th even (resp., odd) pentagonal number [9, \underline{A014633}] (resp., [9, \underline{A014632}]).

Proof. Setting c = −q^{m−c} and b = −q^{c} in (3) and (5), we obtain

(q^{m−c}; q^{m})_{∞}(q^{c}; q^{m})_{∞}(q^{m}; q^{m})_{∞} = f(−q^{m−c}, −q^{c})

= ∑_{j=−∞}^{∞}(−q^{m−c})^{\frac{j(j+1)}{2}} (−q^{c})^{\frac{j(j−1)}{2}} ,

which yields

∑_{j=−∞}^{∞}(−1)^{j}q^{\frac{mj^{2}+(m−2c)j}{2}} = ∏_{k=1}^{∞}(1 − q^{mk−c})(1 − q^{mk−(m−c)})(1 − q^{mk}).  (17)

The generating function for p_{m}^{c} is given by

∑_{i=0}^{∞} p_{m}^{c}(i)q^{i} = ∏_{k=1}^{∞} \frac{1}{(1 − q^{mk−c})(1 − q^{mk−(m−c)})}.

Hence, we can rewrite (17) as

∏_{k=1}^{∞} \frac{1}{(1 − q^{mk−c})(1 − q^{mk−(m−c)})} ∑_{j=−∞}^{∞}(−1)^{j}q^{\frac{mj^{2}+(m−2c)j}{2}} = ∏_{k=1}^{∞}(1 − q^{mk}),

or, equivalently,

∑_{i=0}^{∞} p_{m}^{c}(i)q^{i} ∑_{j=−∞}^{∞}(−1)^{j}q^{\frac{mj^{2}+(m−2c)j}{2}} = ∑_{j=−∞}^{∞}(−1)^{j}q^{\frac{mj(3j−1)}{2}} .

This last identity yields

∑_{i=0}^{∞} p_{m}^{c}(i)q^{i}(1 + ∑_{j=1}^{∞}(−1)^{j}q^{\frac{mj^{2}+(m−2c)j}{2}} + ∑_{j=1}^{∞}(−1)^{j}q^{\frac{mj^{2}−(m−2c)j}{2}} )

= ∑_{n=0}^{∞} (p_{m}^{c}(n) + ∑_{j=1}^{∞}(−1)^{j}p_{m}^{c}(n − (mj^{2} + (m − 2c)j)/2)

+(−1)^{j}p_{m}^{c}(n − (mj^{2} − (m − 2c)j)/2))q^{n}.

Therefore

∑_{j=−∞}^{∞}(−1)^{j}q^{\frac{mj(3j−1)}{2}} = ∑_{n=0}^{∞} (p_{m}^{c}(n) + ∑_{j=1}^{∞}(−1)^{j}p_{m}^{c}(n − (mj^{2} + (m − 2c)j)/2)

+(−1)^{j}p_{m}^{c}(n − (mj^{2} − (m − 2c)j)/2))q^{n},

which completes the proof.

As special cases of Theorem 8, we have the following corollaries which provide recurrence relations for the number of partitions that appear in the well-known Rogers-Ramanujan’s identities.

Corollary 9. Let p_{R1}(n) denote the number of partitions of n whose parts are congruent to ±1 modulo 5 and let p_{R2}(n) denote the number of partitions of n whose parts are congruent to ±2 modulo 5. Then, for all n ≥ 0, we have

p_{R1}(n) − p_{R1}(n − 1) − p_{R1}(n − 4) + p_{R1}(n − 7) + p_{R1}(n − 13) − ⋯
⋯ + (−1)^{j}(p_{R1}(n − j(5j − 3)/2) + p_{R1}(n − j(5j + 3)/2)) + ⋯

= \begin{cases}1, & if n = 5h_{j}^{e}; \\ −1, & if n = 5h_{j}^{o}; \\ 0, & otherwise, \end{cases}

and

p_{R2}(n) − p_{R2}(n − 1) − p_{R2}(n − 2) + p_{R2}(n − 5) + p_{R2}(n − 7) − ⋯
⋯ + (−1)^{j}(p_{R2}(n − j(3j − 1)/2) + p_{R2}(n − j(3j + 1)/2)) + ⋯

= \begin{cases}1, & if n = k_{j}^{e}; \\ −1, & if n = k_{i}^{o}; \\ 0, & otherwise, \end{cases}

where h_{j}^{e} (resp., h_{j}^{o}) is the j-th heptagonal number [9, \underline{A085787}] with j even (resp., odd).

Corollary 10. Let s_{1}(n) denote the number of partitions of n having congruent to ±1 modulo 6 and let s_{2}(n) denote the number of partitions of n whose parts are congruent to ±2 modulo

6. Then, for all n ≥ 0,

s_{1}(n) − s_{1}(n − 1) − s_{1}(n − 5) + s_{1}(n − 8) + s_{1}(n − 16) − ⋯
⋯ + (−1)^{j}(s_{1}(n − j(3j − 2)) + s_{1}(n − j(3j + 2))) + ⋯
= s_{2}(n) − s_{2}(n − 2) − s_{2}(n − 4) + s_{2}(n − 10) + s_{2}(n − 14) − ⋯
⋯ + (−1)^{j}(s_{2}(n − j(3j − 1)) + s_{2}(n − j(3j + 1))) + ⋯

= \begin{cases}1, & if n = 6k_{j}^{e}; \\ −1, & if n = 6k_{i}^{o}; \\ 0, & otherwise. \end{cases}

4 Acknowledgments

This research was supported by São Paulo Research Foundation (FAPESP) (grant no. 2019/10742-0).

References

[1] B. C. Berndt, Number Theory in the Spirit of Ramanujan, American Mathematical Society, 2006.

[2] Y. Choliy, L. W. Kolitsch, and A. V. Sills, Partition recurrences, Integers 18 (2018), Article A1.

[3] S. Corteel and J. Lovejoy, Overpartitions, Trans. Amer. Math. Soc. 356 (2004), 1623– 1635.

[4] J. A. Ewell, Partition recurrences, J. Combin. Theory Ser. A 14 (1973), 125–127.

[5] J. A. Ewell, Another recurrence for the partition function, JP J. Algebra, Number Theory, App. 4 (2004), 147–152.

[6] M. Merca, New recurrences for Euler’s partition function, Turk. J. Math. 41 (2017), 1184–1190.

[7] D. Nyirenda, On parity and recurrences for certain partition functions, Contrib. Discrete Math. 15 (2020), 72–79.

[8] K. Ono, N. Robbins, and B. Wilson, Some recurrences for arithmetical functions, J. Indian Math. Soc. 62 (1996), 29–50.

[9] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2020.

2010 Mathematics Subject Classification: Primary 11P83; Secondary 05A17. Keywords: partition, overpartition, recurrence relation, generating function.

(Concerned with sequences \underline{A000009}, \underline{A000041}, \underline{A000217}, \underline{A000700}, \underline{A001318}, \underline{A014493}, \underline{A014494}, \underline{A014632}, \underline{A014633}, \underline{A015128}, \underline{A027187}, \underline{A027193}, and \underline{A085787}.)

Received September 9 2020; revised version received December 24 2020. Published in Journal of Integer Sequences, December 28 2020.

Return to Journal of Integer Sequences home page.