INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25

COMPUTATION OF q-PARTIAL FRACTIONS

Augustine O. Munagi

The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the

Witwatersrand, Johannesburg 2050, South Africa

                          munagi@maths.wits.ac.za

Received: 8/2/06, Revised: 1/18/07, Accepted: 4/24/07, Published: 5/14/07

Abstract

We study a special partial fraction technique which is designed for rational functions with poles on the unit circle, known as q-fractions. Even though the theory of q-partial fractions has already been applied to the Rademacher Conjecture, no systematic computational development appeared. In this paper we present two algorithms for the computation of q-partial fractions and highlight certain predictable coefficients which arise from the symmetry of the decompositions. We also examine the q-partial fraction content of reciprocals of the cyclotomic polynomials, and indicate how the technique can be used to facilitate the extraction of enumeration formulas from certain power series generating functions.

1. Introduction

The methods to be discussed in this paper have their genesis in the work of P.A. MacMahon who views his work as an extension of that of A. Cayley. The motivation was the need to devise efficient closed forms for the numbers p(n, m) of the partitions of a positive integer n into at most m parts for small m, the generating function of which is given by

a(m, q) = \frac{1}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{m})} , m ≥ 0, |q| < 1.

In the present context the first complete examples of q-partial fraction decompositions are the following expansions given by Cayley [8] and MacMahon [12, p. 63], respectively:

∑_{n=0}^{∞} p(n, 2)q^{n} = a(2, q) = \frac{1/2}{(1 − q)^{2}} + \frac{1/2}{1 − q^{2}}

∑_{n=0}^{∞} p(n, 3)q^{n} = a(3, q) = \frac{1/4}{(1 − q)^{2}} + \frac{1/6}{(1 − q)^{3}} + \frac{1/4}{1 − q^{2}} + \frac{1/3}{1 − q^{3}} .  (1.1)

MacMahon observed that (1.1) resulted in simpler formulas for the functions p(n, 2) and p(n, 3) than the following decompositions recommended by Cayley:

a(2, q) = \frac{1/4}{(1 − q)} + \frac{1/2}{(1 − q)^{2}} + \frac{\frac{1}{4}(1 − q)}{1 − q^{2}}
a(3, q) = \frac{17/72}{1 − q} + \frac{1/4}{(1 − q)^{2}} + \frac{1/6}{(1 − q)^{3}} + \frac{\frac{1}{8}(1 − q)}{1 − q^{2}} + \frac{\frac{1}{9}(q^{2} + q − 2)}{1 − q^{3}}.  (1.2)

Indeed, by comparing the coefficients of q^{n} on both sides of each identity, after each summand on the right side is expanded as a power series about q = 0, the identities in (1.1) give

p(n, 2) = \frac{1}{2}(n + 1) + \frac{1}{2}(1, 0)cr2_{n},
p(n, 3) = \frac{1}{12}(n + 1)(n + 5) + \frac{1}{4}(1, 0)cr2_{n} + \frac{1}{3}(1, 0, 0)cr3_{n},  (1.3)

while the identities in (1.2) lead to

p(n, 2) = \frac{1}{2}n + \frac{3}{4} + \frac{1}{4}(1, −1)pcr2_{n},
p(n, 3) = \frac{1}{12} (n^{2} + 6n + \frac{47}{6}) + \frac{1}{8}(1, −1)pcr2_{n} + \frac{1}{9}(2, −1, −1)pcr3_{n},  (1.4)

where (A_{0}, A_{1}, …, A_{M−1})crM_{n} is the so-called circulator (or circulant) of period M and represents the general coefficient in the power series expansion about q = 0 of the periodic function (A_{0} + A_{1}q + ⋯ + A_{M−1}q^{M−1})/(1 − q^{M}). It is defined by

(A_{0}, A_{1}, …, A_{M−1})crM_{n} = A_{r} if n ≡ r(mod M), 0 ≤ r ≤ M − 1

Cayley’s formulas (1.4) contain the prime circulator (A_{0}, A_{1}, …, A_{M−1})pcrM_{n} which is a circulator subject to the additional conditions A_{c} + A_{c+s} + A_{c+2s} + ⋯ + A_{c+(b−1)s} = 0, 0 ≤ c ≤ s − 1, for every factorization of M into two factors M = sb, with b > 1.

The immediate advantage of the circulator notation is the elimination of complex and irrational quantities from partition formulas [2, 10].

The q-partial fraction technique is specially designed for handling rational functions whose poles consist of roots of unity, i.e., functions of the type:

A(q) = \frac{f(q)}{(1 − q^{n_{1}})^{s_{1}}(1 − q^{n_{2}})^{s_{2}} ⋯ (1 − q^{n_{r}})^{s_{r}}} , |q| < 1,

where the n_{j} and s_{j} are positive integers, 1 ≤ j ≤ r, r > 0, and degree(f)< ∑_{i=1}^{r} n_{i}s_{i}.

These are the q-fractions. Generally, the q-fractions consist of proper rational functions over the field ℚ of rational numbers in which the denominators can be factored into products of cyclotomic polynomials.

Most rational generating functions encountered in Combinatorics and q-Theory are sums and products of q-fractions [1, 3, 4, 7, 9].

Recall that the nth cyclotomic polynomial [16] for a positive integer n is defined by

Φ_{n}(q) = ∏_{d|n}(q^{d} − 1)^{μ(n/d)},  (1.5)

where μ(n) denotes the Möbius function.

It is well-known that the prime circulators appearing in formulas belonging to the class of those in (1.4) are uniquely determined following the uniqueness of the Cayley-type partial fractions. The algorithm for the latter essentially contains two simple steps:

Cayley: Step 1: Obtain the decomposition of the q-fraction into ordinary partial fractions over ℚ, say Σf_{i}(q)/(Φ_{i}(q))^{k}; Step 2: Translate each summand f_{i}(q)/(Φ_{i}(q))^{k} into an equivalent function with denominator of the form (1 − q^{n})^{s}, by multiplying the numerator and denominator with the complementary polynomial (1 − q^{i})^{s}/(Φ_{i}(q))^{k}.

On the other hand, Gupta, et al [10, p. xxv] observed that formulas in the class of those in (1.3), which bear the simplest forms of the circulators, could in general only be found by trial-and-error transformations of partial fractions, when possible. Thus they suggested the problem of discovering a systematic method for the prescribed partial fractions.

The theory of q-partial fractions, which has already appeared in [13], provides a solution to this problem. The primary motivation for the theory there is demonstrated in the application to the proof of a restricted case of the Rademacher Conjecture [15, p. 302], [2]. While reviewing literature afterwards we found that the technique also addressed the formula problem of Gupta and his collaborators.

We show below (Section 4) that q-partial fractions also provide a natural platform for the elimination of the circulators in favour of binomial coefficients. It is then immediate to write down formulas such as

p(n, 4) = ⟨\frac{25}{144}\binom{n + 2}{1} + \frac{1}{8}\binom{n + 2}{2} + \frac{1}{24}\binom{n + 3}{3} + \frac{1}{8}\binom{\frac{n}{2} + 1}{1}⟩;  (1.6)

p(n, 5) = ⟨\frac{11}{64}\binom{n + 2}{1} + \frac{31}{288}\binom{n + 2}{2} + \frac{1}{24}\binom{n + 3}{3} + \frac{1}{120}\binom{n + 4}{4}
+ \frac{1}{16}\binom{\frac{n}{2} + 1}{1}⟩ ,  (1.7)

where ⟨N⟩ is the nearest integer to N and \binom{N}{j} = 0 if N is not an integer.

These formulas should be compared with other representations given in [2, 6, 8, 10].

The aim of this paper is to present certain algorithms for the computation of q-partial fractions together with some special features of the decompositions in order to bring the technique to the knowledge of a broader audience.

The rest of the paper is organized as follows. Section 2 recaps the fundamental theory, and Section 3 is devoted to the description of two algorithms for computing q-partial fractions. Section 4 deals with an application of the technique to the extraction of general coefficients of certain power series. In Section 5 we examine the q-partial fraction content of reciprocals of the cyclotomic polynomials. Lastly, Section 6 profiles a few predictable coefficients in the decomposition of certain q-fractions.

2. The Basic Representation Theorem

The key departure of q-partial fractions from the Cayley-type partial fractions is the stipulation that for a summand v(q)/(1 − q^{n})^{s} to be admissible, the degree of v(q) must be less than Euler’s totient function ϕ(n), rather than the standard requirement that the degree of v(q) be less than ns.

Definition 2.1 The q-fraction v(q)/(1 − q^{n})^{s} is called basic if it satisfies degree(v) < ϕ(n).

Definition 2.2 The q-partial fraction decomposition of the q-fraction A(q) is a representation of A(q) as a finite sum of basic q-fractions with distinct denominators.

Theorem 2.3 For any specified q-fraction, the representation asserted in Definition 2.2 exists, and is unique up to the order of the summands.

Sketch of Proof. We sketch a constructive proof of the theorem by writing the general qfraction A(q) as a sum of basic q-partial fractions. (A non-constructive proof of Theorem 2.3 is given in [13].) We work throughout in the rational field ℚ.

First obtain the ordinary partial fraction decomposition

A(q) = Σf_{i}(q)/(Φ_{i}(q))^{k_{i}}  (2.1)

where deg(f_{i}) < ϕ(i) for each i, k_{i} > 0.

Express each summand f_{i}(q)/(Φ_{i}(q))^{k_{i}} as a sum of basic q-fractions, by first multiplying the numerator and denominator by the factor v_{i}(q) = (1 − q^{i})^{k_{i}}/(Φ_{i}(q))^{k_{i}} to get

\frac{f_{i}(q)}{(Φ_{i}(q))^{k_{i}}} = \frac{1}{v_{i}(q)} (\frac{v_{i}(q)f_{i}(q)}{(Φ_{i}(q))^{k_{i}}}) = \frac{v_{i}(q)f_{i}(q)}{(1 − q^{i})^{k_{i}}}.

If degree(v_{i}f_{i}) < ϕ(i) in the third expression, then we have a single basic q-fraction. Otherwise decompose the parenthesized function in the middle into ordinary partial fractions,

\frac{f_{i}(q)}{(Φ_{i}(q))^{k_{i}}} = \frac{1}{v_{i}(q)} (∑_{j=0}^{k_{i}} \frac{r_{j}(q)}{(Φ_{i}(q))^{k_{i}−j}} ) = \frac{r_{0}(q)}{(1 − q^{i})^{k_{i}}} + ∑_{j=1}^{k_{i}} \frac{r_{j}(q)}{v_{i}(q)(Φ_{i}(q))^{k_{i}−j}}  (2.2)

where degree(r_{j}) < ϕ(i).

But the denominator of the general summand on the right side of (2.2) (except the first), need not be of the required form, and is therefore handled again like A(q), ab initio. This procedure is iteratively continued until we arrive at a single basic q-fraction, preceded by a sum of basic q-fractions with denominators (1 − q^{c})^{x} such that 1 ≤ c ≤ i and 1 ≤ x ≤ k_{i}. The process will terminate since both i and k_{i} are finite.

Thus it follows by mathematical induction on the number of distinct factors of (1 − q^{i})^{k_{i}} of the form (1 − q^{n})^{s} that

\frac{f_{i}(q)}{(Φ_{i}(q))^{k_{i}}} = ∑_{{j \atop d|i}} \frac{r_{j}(q)}{(1 − q^{d})^{c}} , degree(r_{j}) < ϕ(d), c > 0;  (2.3)

and, substituting (2.3) into (2.1), gives A(q) = ∑_{i} ∑_{j, d|i} r_{j}(q)/(1 − q^{d})^{c}.

Thus both the existence and uniqueness of the q-partial fraction decomposition follow from those of the corresponding ordinary partial fraction decomposition. □

3. Algorithms for q-Partial Fractions

We present two algorithms for computing q-partial fractions. The first (Iteratn) is directly prescribed by the proof of Theorem 2.3. The second (UndetCoef) is an adaptation of the familiar method of undetermined coefficients for obtaining ordinary partial fractions.

3.1 Iteratn Decompose the proper rational function f(q)/h(q) into q-partial fractions: (I) If f(q)/h(q) is not a q-fraction, then FAIL; (generally, test if h(q) factors into a product of cyclotomic polynomials). (II) Obtain the ordinary partial fraction decomposition of f(q)/h(q); (III) Transform each summand into a sum of basic q-fractions as explained in the proof of Theorem 2.3; (IV) Substitute into the original decomposition and combine like terms.

Example We derive the second member of (1.1). The ordinary partial fraction decomposition is

\frac{1}{(1 − q)(1 − q^{2})(1 − q^{3})} = \frac{17/72}{1 − q} + \frac{1/4}{(q − 1)^{2}} + \frac{1/6}{(1 − q)^{3}} + \frac{1/8}{q + 1} + \frac{\frac{1}{9}(q + 2)}{q^{2} + q + 1}.  (3.1)

Transform each summand on the right into a sum of basic q-fractions (the first three fractions are already basic):

\frac{1/8}{q + 1} = −\frac{\frac{1}{8}(1 − q)}{(1 + q)(1 − q)} = − \frac{\frac{1}{8}(1 − q)}{1 − q^{2}} = \frac{1}{1 − q} (−\frac{1}{8} + \frac{1/4}{1 + q} )

= \frac{−1/8}{1 − q} + \frac{1/4}{1 − q^{2}} ,  (3.2)

\frac{\frac{1}{9}(q + 2)}{q^{2} + q + 1} = \frac{1}{1 − q} (−\frac{1}{9} + \frac{1/3}{1 + q + q^{2}} ) = \frac{−1/9}{1 − q} + \frac{1/3}{1 − q^{3}} .  (3.3)

Substitute (3.2), (3.3) into (3.1) and add like terms to get the required decomposition:

\frac{1}{(1 − q)(1 − q^{2})(1 − q^{3})} = \frac{1/4}{(1 − q)^{2}} + \frac{1/6}{(1 − q)^{3}} + \frac{1/4}{1 − q^{2}} + \frac{1/3}{1 − q^{3}} .

3.2 UndetCoef Decompose the proper rational function f(q)/h(q) into q-partial fractions: (I) If f(q)/h(q) is not a q-fraction, then FAIL; (II) Re-write f(q)/h(q) as F (q)/H(q), if necessary, so that H(q) is a product of factors of the form (1 − q^{n})^{s} only; (III) Obtain the q-factorization G(q) of H(q): the q-factorization of (1−q^{n_{1}})^{s_{1}}(1−q^{n_{2}})^{s_{2}} ⋯ (1− q^{n_{r}})^{s_{r}} is obtained by replacing each factor 1 − q^{n_{i}} by ∏(1 − q^{d}), where d|n_{i}; (IV) State the theoretical decomposition of f(q)/h(q), i.e., identify the given function with a sum of basic q-fractions with unknown polynomial coefficients f_{i}(q) such that each factor (1 − q^{d})^{k} of G(q) contributes the sum f_{1}(q)/(1 − q^{d}) + ⋯ + f_{k}(q)/(1 − q^{d})^{k}, where degree(f_{j}) < ϕ(d); (V) Clear fractions and compare coefficients of powers of q on both sides to determine unknown coefficients; (VI) Substitute into the theoretical decomposition in (IV).

Example We decompose R(q) into q-partial fractions using UndetCoef. We have

R(q) = \frac{3q^{8} + 5q^{4} + 4q^{2} − 2}{(1 − q^{4})(1 − q^{5})}.

The q-factorization of (1 − q^{4})(1 − q^{5}) is (1 − q)^{2}(1 − q^{2})(1 − q^{4})(1 − q^{5}). Thus we set

R(q) = \frac{A}{1 − q} + \frac{B}{(1 − q)^{2}} + \frac{C}{1 − q^{2}} + \frac{D + Eq}{1 − q^{4}} + \frac{F + Gq + Hq^{2} + Jq^{3}}{1 − q^{5}} .  (3.4)

(Note that each summand v(q)/(1 − q^{d})^{k} on the right side satisfies degree(v) < ϕ(d).)

It is a routine matter to clear fractions and compare coefficients of powers of q on both sides to obtain A = −3, B = 1/2, C = 5/2, D = 1, E = 1, F = −3, G = 1, H = 3, J = 1.

Then substitute for the coefficients in (3.4) to obtain the required decomposition:

\frac{3q^{8} + 5q^{4} + 4q^{2} − 2}{(1 − q^{4})(1 − q^{5})} = \frac{−3}{1 − q} + \frac{1/2}{(1 − q)^{2}} + \frac{5/2}{1 − q^{2}} + \frac{1 + q}{1 − q^{4}} + \frac{−3 + q + 3q^{2} + q^{3}}{1 − q^{5}} .

Remarks. Iteratn is the algebraically more complicated of the two algorithms since it subsumes a full classical partial fraction algorithm over ℚ. Clearly the version of the latter which employs the Euclidean algorithm may not be adapted to q-partial fractions because the concept of relative primeness is irrelevant to q-factorization.

The expansion of A(q) into q-partial fractions contains at most s_{1}τ(n_{1}) + ⋯ + s_{r}τ(n_{r}) summands, which is the same number as in the ordinary partial fraction algorithm, where τ(N) is the number of positive divisors of N. In particular the number of unknown coefficients to be computed by UndetCoef for a(q) is ∑_{1≤k≤m} ⌊\frac{m}{k}⌋ ϕ(k) = (m + 1)m/2, where ⌊N⌋ is the floor function.

We deduce that the decomposition of A(q) into q-partial fractions is at worst as computationally costly as the ordinary partial fraction decomposition of A(q) over ℚ, using the corresponding versions of UndetCoef. The determination of the coefficients of basic q-fractions is much simplified by one or more of the following nice situations:

• The q-factorization of the function 1 − q^{n} is obviously easier than the ordinary factorization over the integers.

• Certain coefficients are predictable (see Section 6). In particular the coefficient of the basic fraction 1/(1 − q) is mostly 0 (Theorem 6.1).

• The denominators of basic q-fractions have larger degrees than those of ordinary partial fraction summands. So the clearing of fractions reduces the magnitude of coefficients of powers of q, thus simplifying the system of equations to be solved.

4. Application to Enumeration Formulas

We give an illustration with a typical ordinary power series generating function. In this section and the next, the q-fraction 1/(1 − q^{n})^{s} is also represented by F_{n}^{s}.

Let T (n) denote the number of triangles with integer sides and perimeter n. Hirschhorn [11] derives the formula

T (n) = \{ \begin{matrix}⟨n^{2}/48⟩ , & if n is even \\ ⟨(n + 3)^{2}/48⟩ , & if n is odd \end{matrix}  (4.1)

where ⟨N⟩ is the nearest integer to N.

His method involves a combinatorial argument, followed by the application of the wellknown formula: p(n, 3) = ⟨(n + 3)^{2}/12⟩.

We give an alternative derivation of (4.1) from the generating function for T (n) ([5, p. 557]) via q-partial fractions. Consider the q-partial fraction expansion

∑_{n=0}^{∞} T (n)q^{n} = q^{3}F_{2}F_{3}F_{4}
= \frac{1}{16}F_{1}^{2} + \frac{1}{24}F_{1}^{3} + \frac{1}{16}F_{2} − \frac{1}{4}F_{2}^{2} + \frac{1}{3}F_{3} − \frac{1}{4}(1 + q)F_{4}.  (4.2)

If we expand each summand on the right as a power series about q = 0, and then equate the coefficients of q^{n} on both sides, we first obtain the exact formula

T (n) = \frac{n^{2} + 6n + 5}{48} − \frac{1}{4} (\frac{n}{2} + 1) (1, 0)cr2_{n} + \frac{1}{16}(1, 0)cr2_{n}
+ \frac{1}{3}(1, 0, 0)cr3_{n} − \frac{1}{4}(1, 1, 0, 0)cr4_{n}.  (4.3)

Thus, if n is even we have

T (n) = \frac{n^{2}}{48} + \frac{5}{48} − \frac{1}{4} + \frac{1}{16} + \frac{1}{3}(1, 0, 0)cr3_{n} − \frac{1}{4}(1, 1, 0, 0)cr4_{n}.  (4.4)

But noticing that

|\frac{5}{48} − \frac{1}{4} + \frac{1}{16} + \frac{1}{3}(1, 0, 0)cr3_{n} − \frac{1}{4}(1, 1, 0)cr4_{n}| ≤ |\frac{5}{48} − \frac{1}{4} + \frac{1}{16} + \frac{1}{3}| < \frac{1}{2},

we can subtract the terms before the first inequality from the right side of (4.4) to obtain the first part of (4.1).

If n is odd then (4.3) becomes

T (n) = \frac{N^{2} + 6n + 5}{48} + \frac{1}{3}(1, 0, 0)cr3_{n} − \frac{1}{4}(1, 1, 0, 0)cr4_{n},

and since

|\frac{1}{3}(1, 0, 0)cr3_{n} − \frac{1}{4}(1, 1, 0, 0)cr4_{n}| − \frac{1}{12} ≤ \frac{1}{3} − \frac{1}{12} < \frac{1}{2},

we can subtract the terms before the first inequality from the right side to obtain the second part of (4.1). □

The simplicity of the coefficients of basic q-fractions makes it convenient to read off formulas directly from expansions.

If the definition of the binomial coefficient is slightly adjusted to read, for a nonnegative integer K,

\binom{N}{K} = \{ \begin{matrix}\frac{N!}{K!(N−K)!}, & if N is an integer and N ≥ K, \\ 0, & otherwise, \end{matrix}

then the circulator may be replaced by a sum of binomial coefficients:

(A_{0}, …, A_{M−1})crM_{n} = ∑_{k=0}^{M−1} A_{k}\binom{\frac{n−k}{M}}{0}.

It is now routine to read off the following formula directly from (4.2):

T (n) = ⟨\frac{1}{16}\binom{n + 1}{1} + \frac{1}{24}\binom{n + 2}{2} − \frac{1}{4}\binom{\frac{n}{2} + 1}{1}⟩ .  (4.5)

Similarly, beginning with the decompositions,

F_{1}F_{2}F_{3}F_{4} = \frac{25}{144}F_{1}^{2} + \frac{1}{8}F_{1}^{3} + \frac{1}{24}F_{1}^{4} + \frac{1}{16}F_{2} + \frac{1}{8}F_{2}^{2} + \frac{1}{9}(2 + q)F_{3} + \frac{1}{4}F_{4},
F_{1}F_{2}F_{3}F_{4}F_{5} = \frac{11}{64}F_{1}^{2} + \frac{31}{288}F_{1}^{3} + \frac{1}{24}F_{1}^{4} + \frac{1}{120}F_{1}^{5} + \frac{11}{64}F_{2} + \frac{1}{16}F_{2}^{2}

+ \frac{1}{9}(2 + q)F_{3} + \frac{1}{8}(1 + q)F_{4} + \frac{1}{5}F_{5},

one reads off the formulas (1.6) and (1.7) respectively. Obviously such formulas for p(n, m) continue for larger m.

To specify the above formulas, we note, for instance, the following version of (4.3) in which binomial coefficients correspond one-to-one with the summands in (4.2):

T (n) = \frac{1}{16}\binom{n + 1}{1} + \frac{1}{24}\binom{n + 2}{2} + \frac{1}{16}\binom{\frac{n}{2}}{0} − \frac{1}{4}\binom{\frac{n}{2} + 1}{1} + \frac{1}{3}\binom{\frac{n}{3}}{0}

− \frac{1}{4}\binom{\frac{n}{4}}{0} − \frac{1}{4}\binom{\frac{n−1}{4}}{0}.

Then (4.5) follows from the fact that

|\frac{1}{16}\binom{\frac{n}{2}}{0} + \frac{1}{3}\binom{\frac{n}{3}}{0} − \frac{1}{4}\binom{\frac{n}{4}}{0} − \frac{1}{4}\binom{\frac{n−1}{4}}{0}| ≤ |\frac{1}{16} + \frac{1}{3}| < \frac{1}{2}.

5. Reciprocals of Cyclotomic Polynomials

In this section we find the q-partial fraction decomposition of the reciprocal of the cyclotomic polynomial (1.5) for some values of n.

The factorization of q^{n} − 1 over the integers q^{n} − 1 = ∏_{d|n} Φ_{d}(q), gives the following recursion for the cyclotomic polynomials:

Φ_{1}(q) = q − 1, Φ_{n}(q) = \frac{q^{n} − 1}{∏_{d|n, d<n} Φ_{d}(q)}, n ≥ 2.

This in turn gives

\frac{1}{Φ_{n}(q)} = \frac{− ∏_{d|n, d<n} Φ_{d}(q)}{1 − q^{n}}, n ≥ 2.  (5.1)

Thus (Φ_{n}(q))^{−1} is equivalent to a standard q-fraction with a single denominator factor. It follows that the q-partial fraction decomposition of (Φ_{n}(q))^{−1} has exactly one summand if n < 2ϕ(n). Such q-partial fraction decompositions are called trivial and may be obtained by applying Cayley to (Φ_{n}(q))^{−1}.

Clearly the decomposition of (Φ_{n}(q))^{−1} cannot be trivial if n is even. We observe that (Φ_{n}(q))^{−1} has nontrivial decompositon if and only if (Φ_{m}(q))^{−1} does, where m denotes the largest squarefree divisor of n.

The next theorem determines all trivial q-partial fraction decompositions of (Φ_{n}(q))^{−1} when n is at most the product of powers of four distinct primes. The straightforward derivation is omitted.

Theorem 5.1 Let N be an odd number with the factorization N = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{r}^{m_{r}} into primes p_{i}, p_{1} < p_{2} < ⋯ < p_{r}, where m_{i} ≥ 1, r ≥ 1. Then the q-partial fraction decomposition of (Φ_{N}(q))^{−1} is trivial only in the following cases, for 1 ≤ r ≤ 4:

(i) r = 1, 2;

(ii) r = 3, excluding all N determined by (p_{1}, p_{2}, p_{3}) = (3, 5, 7), (3, 5, 11), (3, 5, 13);

(iii) r = 4, excluding all N determined by members of the sets

(a) {(3, 5, 7, p_{4}) | p_{4} > 7}, {(3, 5, 11, p_{4}) | p_{4} > 11}, {(3, 5, 13, p_{4}) | p_{4} > 13};

(b) {(3, 5, 17, p_{4}) | 19 ≤ p_{4} ≤ 251},

(c) {(3, 5, 19, p_{4}) | 23 ≤ p_{4} ≤ 89},

(d) {(3, 5, 23, p_{4}) | 29 ≤ p_{4} ≤ 47},

(e) {(3, 5, 29, 31)},

(f) {(3, 7, 11, p_{4}) | 13 ≤ p_{4} ≤ 23},

(g) {(3, 7, 13, 17)}.

Theorem 5.2 Let k, m, n denote positive integers and let p, p_{1}, p_{2} be odd primes, p_{1} < p_{2}. The following q-partial fraction decompositions are valid.

(i) (Φ_{2^{k}}(q))^{−1} = −F_{2^{k−1}} + 2F_{2^{k}}.

(ii) (Φ_{2^{k}p^{m}}(q))^{−1} = (−F_{2^{k−1}p^{m}} + 2F_{2^{k}p^{m}}) ∏_{i=0}^{m−1} Φ_{2^{k}p^{i}}(q), p ≥ 5.

(iii) (Φ_{2^{k}p_{1}^{m}p_{2}^{n}}(q))^{−1} = (−F_{2^{k−1}p_{1}^{m}p_{2}^{n}} + 2F_{2^{k}p_{1}^{m}p_{2}^{n}}) ( ∏_{i=0}^{n−1} Φ_{2^{k}p_{1}^{m}p_{2}^{i}}(q)) ( ∏_{s=0}^{m−1} ∏_{j=0}^{n} Φ_{2^{k}p_{1}^{s}p_{2}^{j}(q)}) ,

p_{1} ≥ 5.

Proof. For (i), we apply Iteratn to get

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

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

For (ii), write (Φ_{2^{k}p^{m}}(q))^{−1} = Φ_{2^{k}}(q^{p^{m−1}})(Φ_{2^{k}}(q^{p^{m}}))^{−1}. Hence using part (i) we obtain (Φ_{2^{k}p^{m}}(q))^{−1} = Φ_{2^{k}}(q^{p^{m−1}})(−F_{2^{k−1}p^{m}} + 2F_{2^{k}p^{m}}), which simplifies to the desired result. For the first summand to be basic, we need degree(Φ_{2^{k}}(q^{p^{m−1}})) < ϕ(2^{k−1}p^{m}), or 2^{k−1}p^{m−1} < 2^{k−2}(p − 1)p^{m−1}, or p ≥ 5.

The proof of (iii) is analogous to that of part (ii). □

Remark The decomposition in Theorem 5.2 (ii) merely fails to hold in general when p = 3. For instance, it holds for (Φ_{18}(q))^{−1}, but fails for (Φ_{12}(q))^{−1} (= −F_{2}+qF_{3}−qF_{6}+2Φ_{4}(q)F_{12}.) An analogous remark applies to Theorem 5.2 (iii).

6. Computation of Special Coefficients

We highlight certain predictable coefficients in the q-partial fraction decompositions of A(q) and a(q).

In the hope of extending the proof in [13], which is based on the coefficient of (1−q)^{−1}, we compute the coefficient of (1 − q)^{−2} in the q-partial fraction decomposition of f(q)/(1 − q^{n})^{s}, when f(q) is a polynomial function of specified type.

We will use the notation {g(q)}F (q) to denote the coefficient of the basic q-fraction g(q) in the q-partial fraction expansion of F (q).

The following result is established in [13].

Theorem 6.1(Munagi [13])

\{(1 − q)^{−1}\}A(q) = \{ \begin{matrix}(−1)^{s_{1}+s_{2}+···+s_{r}−1}lc(f), & if degree(f) = ∑_{i=1}^{r} n_{i}s_{i} − 1 \\ 0, & if degree(f) < ∑_{i=1}^{r} n_{i}s_{i} − 1 \end{matrix}

where lc(f) is the leading coefficient of f(q).

Theorem 6.2 If r > 1, or r = 1 and n_{1} = 1, in A(q), then with the notation s = ∑_{i=1}^{r} s_{i}, we have

\{(1 − q)^{−s}\}A(q) = \frac{f(1)}{n_{1}^{s_{1}}n_{2}^{s_{2}} ⋯ n_{r}^{s_{r}}} .

Proof. For r > 0 let the theoretical decomposition of A(q) via UndetCoef be given by

\frac{f(q)}{h(q)} ≡ \frac{C_{1,s,0}}{(1 − q)^{s}} + \frac{C_{1,s−1,0}}{(1 − q)^{s_{1}}} + ⋯ + \frac{C_{1,1,0}}{(1 − q)}

+ ∑_{d≥2} ∑_{j≥1} \frac{C_{d,j,0} + C_{d,j,1}q + ⋯ + C_{d,j,ϕ(d)−1}q^{ϕ(d)−1}}{(1 − q^{d})^{j}} ,

where h(q) = (1 − q^{n_{1}})^{s_{1}}(1 − q^{n_{2}})^{s_{2}} ⋯ (1 − q^{n_{r}})^{s_{r}}. Multiply through with h(q) to obtain

f(q) = C_{1,s,0}(1 + q + ⋯ + q^{n_{1}−1})^{s_{1}}(1 + q + ⋯ + q^{n_{2}−1})^{s_{2}} ⋯ (1 + q + ⋯ + q^{n_{r}−1})^{s_{r}}
+ (terms in (1 − q)).

Setting q = 1 in the last expression proves the theorem. □

Corollary 6.3 Some coefficient formulas in the q-partial fraction decomposition of a(m, q):

(1) {(1 − q)^{−1}} a(m, q) = 1/m, {(1 − q)^{−m}} a(m, q) = 1/m!, m ≥ 1;

(2) For each m > 2 there is a sequence of coefficients {(1 − q)^{−(m−k)}} a(m, q), 1 ≤ k ≤ ⌊\frac{m−1}{k}⌋, with the following initial terms.

(i)

\{(1 − q)^{−(m−1)}\}a(m, q) = \frac{1}{4(m − 2)!}, m ≥ 3,

(ii)

\{(1 − q)^{−(m−2)}\}a(m, q) = \frac{26 − 13m + 9m^{2}}{288(m − 2)!} , m ≥ 5,

(iii)

\{(1 − q)^{−(m−3)}\}a(m, q) = \frac{56 − 42m + 33m^{2} − 10m^{3} + 3m^{4}}{1152(m − 2)!} , m ≥ 7.

Proof. The proofs follow from Theorem 6.2, and Cayley’s formula [4, p.81], given by

\frac{1}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{m})} = ∑ \frac{1}{1^{p_{1}}2^{p_{2}} ⋯ m^{p_{m}}p_{1}!p_{2}! ⋯ p_{m}!}

× \frac{1}{(1 − q)^{p_{1}}(1 − q^{2})^{p_{2}} ⋯ (1 − q^{m})^{p_{m}}}  (6.1)

where the summation runs over all partitions (1^{p_{1}}, 2^{p_{2}}, 3^{p_{3}}, …, m^{p_{m}}) of m, with p_{j} ≥ 0, 1 ≤ j ≤ m.

First, evaluate the right side of (6.1) at the partitions (1^{m}) and (m^{1}) to get, respectively,

\frac{1/m!}{(1 − q)^{m}} and \frac{1/m}{1 − q^{m}} ,

which, since they are basic q-fractions, prove part (1).

For part (2), each {(1 − q)^{−m+k}}a(m, q), k ≥ 1, receives contributions, via (6.1), from a finite set of partitons of m of the form

(1^{−m+j}π(j, c)_{>1}), j ≥ 2, 1 ≤ c ≤ k  (6.2)

where π(j, c)_{>1} is a partition of j into c parts, each > 1. For fixed j, it follows that k = j −c. Hence, the total number of contributing partitions is exactly p(1) + p(2) + ⋯ + p(k), where p(N) is the number of all partitions of N.

A series of basic fractions generated by a partition can be obtained using (6.1) and Theorem 6.2. For example, evaluating the right side of (6.1) at (1^{m−2}2) gives

Q(1^{m−2}2) = \frac{1}{2(m − 2)!(1 − q)^{m−2}(1 − q^{2})};

on applying Theorem 6.2 to 2(m − 2)!Q(1^{m−2}2) and subtracting, we obtain

Q(1^{m−2}2) = \frac{1}{2(m − 2)!} (\frac{1/2}{(1 − q)^{m−1}} + \frac{1/2}{(1 − q)^{m−3}(1 − q^{2})}) .

Iterating this procedure, gives, after four steps,

Q(1^{m−2}2) = \frac{1}{2(m − 2)!} (\frac{1/2}{(1 − q)^{m−1}} + \frac{1/4}{(1 − q)^{m−2}} + \frac{1/8}{(1 − q)^{m−3}} + \frac{1/16}{(1 − q)^{m−4}} + ⋯)

Similarly,

Q(1^{m−3}3) = \frac{1}{3(m − 3)!} (\frac{1/3}{(1 − q)^{m−2}} + \frac{1/3}{(1 − q)^{m−3}} + \frac{2/9}{(1 − q)^{m−4}} + \frac{1/9}{(1 − q)^{m−5}} + ⋯)

Q(1^{m−4}2^{2}) = \frac{1}{8(m − 4)!} (\frac{1/4}{(1 − q)^{m−2}} + \frac{1/4}{(1 − q)^{m−3}} + \frac{3/16}{(1 − q)^{m−4}} + \frac{1/8}{(1 − q)^{m−5}} + ⋯)

Q(1^{m−4}4) = \frac{1}{4(m − 4)!} (\frac{1/4}{(1 − q)^{m−3}} + \frac{3/8}{(1 − q)^{m−4}} + \frac{5/16}{(1 − q)^{m−5}} + \frac{5/32}{(1 − q)^{m−2}} + ⋯)

Thus part 2(i) is given by the first term of Q(1^{m−2}2), and 2(ii) by the sum of coefficients of terms from Q(1^{m−2}2), Q(1^{m−3}3), and Q(1^{m−4}2^{2}), that is,

\{(1 − q)^{−(m−2)}\} a(m, q) = \frac{1/4}{2(m − 2)!} + \frac{1/3}{3(m − 3)!} + \frac{1/4}{8(m − 4)!} = \frac{26 − 13m + 9m^{2}}{288(m − 2)!} ,

and so forth. Finally, note that (6.2) implies m > j = k + c, which implies that m > 2k, for fixed m. So the degree of the polynomial numerator of each coefficient is (2k − 1) − 2 + 1 = 2(k − 1). □

Theorem 6.4 For m > 0, let

B(q) = \frac{b_{0} + b_{1}q + b_{2}q^{2} + ⋯ + b_{(m+1)(n−1)}q^{(m+1)(n−1)}}{(1 − q^{n})^{m+1}} .

Then

\{(1 − q)^{−2}\}B(q) = \frac{1}{m!n^{m}} ∏_{s=1}^{m}(sn + 1) ∑_{u=1}^{m}(−1)^{u+1} \frac{∏_{1≤k≤m−u}(kn − 1)}{∏_{u≤p≤m}(pn + 1)}b_{un−1}.

To prove Theorem 6.4 we will need the following lemma.

Lemma 6.5 Let n, d, k be positive integers such that d|n, d ≥ 2 and 1 ≤ k ≤ N; also let

F (q) = \frac{C_{0} + C_{1}q + ⋯ + C_{ϕ(d)−1}q^{ϕ(d)−1}}{(1 − q^{d})^{k}} .

Then the polynomial F (q)(1 − q^{n})^{N} has no terms in q^{in−1}, 1 ≤ i ≤ N.

Proof. We have

F (q)(1 − q^{n})^{N} = \frac{C_{0} + C_{1}q + ⋯ + C_{ϕ(d)−1}q^{ϕ(d)−1}(1 − q^{n})^{N}}{(1 − q^{d})^{k}}

= (C_{0} + C_{1}q + ⋯ + C_{ϕ(d)−1}q^{ϕ(d)−1}) (1 + q^{d} + q^{2d} + ⋯ + q^{n−d})^{k} (1 − q^{n})^{N−k}.

When expanded, the set X of degrees of the terms on the right side is given by

X = {s + kdt + (N − k)u | 0 ≤ s ≤ ϕ(d) − 1, 0 ≤ t ≤ n/d − 1, u = 0, n}.

If in − 1 belongs to X then s = in − 1 (with t = 0 = u) for some i, ⇒ 0 ≤ in − 1 ≤ ϕ(d) − 1. But this contradicts: d > 1 and d|n ⇒ in > ϕ(d). □

Proof of Theorem 6.4 Let {(1−q)^{−2}}B(q) be represented by C_{120}. We employ UndetCoef. The theoretical decomposition of B(q) into q-partial fractions is given by

B(q) = ∑_{r=0}^{(n−1)(m+1)} b_{r}q^{r}(1 − q^{n})^{−m−1} = ∑_{k=2}^{m+1} \frac{C_{1,k,0}}{(1 − q)^{k}} + ∑_{{d|n \atop d≥2}} ∑_{k=1}^{m+1} \frac{P_{d,k}(q)}{(1 − q^{d})^{k}}  (6.3)

where P_{d,k}(q) = C_{d,k,0} + C_{d,k,1} q + ⋯ + C_{d,k,ϕ(d)−1} q^{ϕ(d)−1}. Since the degree of the numerator of B(q) exceeds the degree of the denominator by m + 1 ≥ 2 it follows, by Theorem 6.1, that {(1 − q)^{−1}}B(q) vanishes in the right side of (6.3).

Multiplying both sides of (6.3) by (1 − q^{n})^{m+1} gives

∑_{r=0}^{(n−1)(m+1)} b_{r}q^{r} = ∑_{k=2}^{m+1} \frac{C_{1,k,0}(1 − q^{n})^{m+1}}{(1 − q)^{k}} + T (q),  (6.4)

where

T (q) = ∑_{{d|n \atop d≥2}} ∑_{k=1}^{m+1} \frac{P_{d,k}(q)(1 − q^{n})^{m+1}}{(1 − q^{d})^{k}} .

By Lemma 6.5, T (q) has no terms in q^{in−1}, 1 ≤ i ≤ m, and the powers q^{in−1} on both sides completely determine the coefficients C_{1,k,0}. We note that

\frac{(1 − q^{n})^{m+1}}{(1 − q)^{k}} = ∑_{s=0}^{m+1} \binom{m + 1}{s}(−q^{n})^{s} ∑_{c≥0} \binom{c + k − 1}{c}q^{c}

= ∑_{N≥0} q^{N} ∑_{s=0}^{m+1}(−1)^{s}\binom{m + 1}{s}\binom{N + k − 1 − sn}{k − 1},

where c + sn = N. Hence (6.4) becomes

∑_{r=0}^{(n−1)(m+1)} b_{r}q^{r} = ∑_{k=2}^{m+1} C_{1,k,0} ∑_{N≥0} q^{N} ∑_{s=0}^{m+1}(−1)^{s}\binom{m + 1}{s}\binom{N + k − 1 − sn}{k − 1} + T (q)

= ∑_{k=2}^{m+1} C_{1,k,0} \{∑_{r=0}^{m+1}(−1)^{r}\binom{m + 1}{s}\binom{in + k − 2 − sn}{k − 1}q^{in−1}

+ (terms in q^{v}, v ≠ in − 1, 1 ≤ i ≤ m)} + T (q).

Observe that s can be restricted to the range 1 ≤ s ≤ i−1 since \binom{in+k−2−sn}{k−1} ≥ 0 ⇔ s ≤ i−1.

∑_{r=0}^{(n−1)(m+1)} b_{r}q^{r} = ∑_{k=2}^{m+1} C_{1,k,0} \{∑_{s=0}^{i−1}(−1)^{s}\binom{m + 1}{s}\binom{(i − s)n + k − 2}{k − 1}q^{in−1}

+ (terms in q^{v}, v ≠ in − 1, 1 ≤ i ≤ m)} + T (q).

To determine the C_{1,k,0}, equate the coefficients of the q^{in−1} on both sides to obtain the system of m equations

∑_{k=2}^{m+1} C_{1,k,0}\binom{n+k−2}{k−1} = b_{n−1} ; ∑_{k=2}^{m+1} C_{1,k,0} ∑_{s=0}^{1}(−1)^{s}\binom{m+1}{s}\binom{(2−s)n+k−2}{k−1} = b_{2n−1} ; ⋮ ; ∑_{k=2}^{m+1} C_{1,k,0} ∑_{s=0}^{m−1}(−1)^{s}\binom{m+1}{s}\binom{(m−s)n+k−2}{k−1} = b_{nm−1} .

That is, Ac̄ = b̄, where (j ≡ k − 1)

(A)_{ij} = ∑_{s=0}^{i−1}(−1)^{s}\binom{m + 1}{s}\binom{(i − s)n + j − 1}{j}, c̄ = [ C_{1,2,0} ; ⋮ ; C_{1,m+1,0} ] , b̄ = [ b_{n−1} ; ⋮ ; b_{mn−1} ] .

Let the matrix obtained by replacing the first column of A with b̄ be A_{1}. Then, according to Cramer’s Rule,

\{(1 − q)^{−2}\}B(q) = C_{1,2,0} = \frac{det(A_{1})}{det(A)}.  (6.5)

Let Λ_{1}^{u} denote the matrix obtained from A after deleting the uth row and first column. Then

det(A_{1}) = ∑_{u=1}^{m}(−1)^{u+1} det(Λ_{1}^{u})b_{un−1}.

Thus (6.5) becomes

\{(1 − q)^{−2}\}B(q) = \frac{1}{det(A)} ∑_{u=1}^{m}(−1)^{u+1} det(Λ_{1}^{u})b_{un−1}.  (6.6)

Claim. det(A) = n^{m(m+1)/2}

We use elementary row operations to evaluate det(A). Since

(A)_{ij} = \binom{in + j − 1}{j} + ∑_{s=1}^{i−2}(−1)^{s}\binom{m + 1}{s}\binom{(i − s)n + j − 1}{j} + \binom{n + j − 1}{j},

it follows that det(A) = det(C), where C is the matrix defined by

(C)_{ij} = \binom{in + j − 1}{j}, 1 ≤ i ≤ m, 1 ≤ j ≤ m,

and is obtained on applying the following operations successively to the rows of A:

R_{i} ↦ R_{i} − ∑_{k=1}^{i−1}(−1)^{k}\binom{m + 1}{k}R_{i−k}, 2 ≤ i ≤ j,  (6.7)

where R_{i} denotes the ith row and the other symbols have their usual meanings. The result then follows from the fact that det(C) is a special “combinatorial determinant” [17] corresponding to the case f = 1 + x (see [17, p. 3]). But our row operations approach yields

det(A) = det(C) = \frac{nn^{2} ⋯ n^{m}}{1!2! ⋯ (m − 1)!}V (1, 2, …, m)

where V (x_{1}, x_{2}, …, x_{N}) = ∏_{1≤j≤i≤N}(x_{i} − x_{j}) is the Nth order Vandermonde determinant. Since V (1, 2, …, m) = 1!2! ⋯ (m − 1)!, we obtain det(A) = n^{m(m+1)/2} as claimed.

Substituting for det(A) in (6.6) gives

\{(1 − q)^{−2}\}B(q) = \frac{1}{n^{m(m+1)/2}} ∑_{u=1}^{m}(−1)^{u+1} det(Λ_{1}^{u})b_{un−1}.  (6.8)

It remains to evaluate det(Λ_{1}^{u}). We prove the following Lemma, from which Theorem 6.4 clearly follows. □

Lemma 6.6

det(Λ_{1}^{u}) = \frac{n^{m(m−1)/2}}{m!} \frac{∏_{1≤s≤m}(sn + 1) ∏_{1≤k≤m−u}(kn − 1)}{∏_{u≤p≤m}(pn + 1)}.

Proof. We apply the following modified form of the row operations (6.7) successively to the rows of Λ_{1}^{u}, in order:

R_{i} ↦ R_{i} − ∑_{k=1}^{s}(−1)^{i−k}\binom{m + 1}{i − k}R_{k}, 2 ≤ i ≤ j − 1, s = min(u − 1, i − 1); (6.9)

R_{i} ↦ R_{i} − ∑_{k=u}^{i−1}(−1)^{i−k}\binom{m + 1}{i − k}R_{k}, u + 1 ≤ i ≤ j − 1.  (6.10)

The resulting (m − 1)-square matrix Y_{1}^{u} is given by

(Y_{1}^{u})_{ij} = \{ \begin{matrix}\binom{in+j−1}{j}, & 1 ≤ i < u \\ \binom{(u+t)n+j−1}{j} − E(m, t)\binom{un+j−1}{j}, & 1 ≤ t ≤ m − u \end{matrix} .  (6.11)

We claim that

E(m, t) = \binom{m + t}{t}.  (6.12)

The proof is by induction on the number t of rows u, u + 1, … in which every entry has exactly two summands following applications of the row operations (6.9) to all the rows, and (6.10) down to the (u + t)th row. For brevity denote Ψ(i) = \binom{in+j−1}{j}.

By the definition of the matrix A the effect of the row operations (6.9) down to the uth row is the general uth-row entry Ψ(u + 1) − E(m, 1)Ψ(u). Hence (6.12) holds for t = 1. Assume that (6.12) is true for all positive integers up to t − 1, i.e., the rows from number u through u + t − 2 all have the required form. Then application of the row operations (6.10) to the (u + t − 1)^{st} row gives

R_{u+t−1} ↦ R_{u+t−1} − ∑_{k=u}^{u+t−2}(−1)^{u+t−1−k}\binom{m + 1}{u + t − 1 − k}R_{k}

= ∑_{s=0}^{t}(−1)^{s}\binom{m + 1}{s}Ψ(u + t − s)

− ∑_{k=u}^{u+t−2}(−1)^{u+t−1−k}\binom{m + 1}{u + t − 1 − k}(Ψ(k + 1) − E(m, k − u + 1)Ψ(u))

= Ψ(u + t) + (−1)^{t}\binom{m + 1}{t}Ψ(u) + ∑_{s=1}^{t−1}(−1)^{s}\binom{m + 1}{s}E(m, t − s)Ψ(u)

= Ψ(u + t) + ∑_{s=1}^{t}(−1)^{s}\binom{m + 1}{s}E(m, t − s)Ψ(u).

The last step in the proof is to establish the Vandermonde-convolution-type identity

∑_{k=1}^{t}(−1)^{k}\binom{m + 1}{k}\binom{m + t − k}{t − k} = −\binom{m + t}{t}.  (6.13)

Let S_{t} denote the left side:

S_{t} = ∑_{k=0}^{t−1}(−1)^{k+1}\binom{m + 1}{k + 1}\binom{m + t − k − 1}{m} = ∑_{k} a_{k},

where a_{0} = −(m + 1)\binom{m+t−1}{m}. Then we obtain

\frac{a_{k+1}}{a_{k}} = \frac{(k − m)(k − t + 1)}{(k + 2)(k − m − t + 1)} \frac{(k + 1)}{(k + 1)},

after routine simplification. Thus S_{t} can be written in hypergeometric notation as follows

S_{t} = a_{0} _{3}F_{2} ( \begin{matrix}−m, −t + 1, 1 \\ & , 1 \\ 2, −m − t + 1 \end{matrix} ) .

By setting a = −m, b = 1, n = t − 1, c = 2 and noting that −m − t + 1 = 1 + a + b − c − n, we see that the _{3}F_{2}-term satisfies the Pfaff-Saalschutz Theorem [5, p. 69], namely

3F_{2} ( \begin{matrix}1, −n , b \\ & , 1 \\ c, 1 + a + b − c − n \end{matrix} ) = \frac{(c − a)_{n}(c − b)_{n}}{(c)_{n}(c − a − b)_{n}} ,

where the Pochhammer symbol (x)_{k} is defined by (x)_{k} = x(x + 1) ⋯ (x + k − 1), k ≥ 1, (x)_{0} = 1. Hence

S_{t} = a_{0} · \frac{(2 + m)_{t−1}(1)_{t−1}}{(2)_{t−1}(1 + m)_{t−1}} = −(m + 1)\binom{m + t − 1}{m} · \frac{(2 + m)_{t−1}(1)_{t−1}}{(2)_{t−1}(1 + m)_{t−1}}

which gives, after simplification, S_{t} = −\binom{m+t}{t} = −E(m, t). Hence the claim follows. □

Remark Call (6.13) an identity of order 0. If we concentrate on retaining exactly three summands per entry from the (u + 1)st row downward, the coefficients of Ψ(u) will lead, as above, to the analogous identity of order 1:

∑_{k=1}^{t}(−1)^{k+1}\binom{m + 1}{k + 1}\binom{m + t − k}{t − k} = t\binom{m + t}{t + 1}.

By a similar argument it can be shown that the identity of order 2 is

∑_{k=1}^{t}(−1)^{k+1}\binom{m + t}{k + 2}\binom{m + t − k}{t − k} = \binom{t + 1}{2}\binom{m + t}{t + 2}.

The general form of such identities of fixed order d, 0 ≤ d ≤ m − t + 1, with 1 ≤ t ≤ m, is given by

∑_{k=1}^{t}(−1)^{k+1}\binom{m + 1}{k + d}\binom{m + t − k}{t − k} = \binom{t + d − 1}{d}\binom{m + t}{t + d}.

Remark We recall an important property of determinants [14, p. 2]. Let D, U, V be determinants of order n with ij-entries given by (D)_{ij}, (U)_{ij}, (V)_{ij}, such that for a fixed index k, 1 ≤ k ≤ n, we have

(D)_{ik} = αx_{ik} + βy_{ik}, (U)_{ik} = αx_{ik}, (V)_{ik} = βy_{ik}, and (D)_{ij} = (U)_{ij} = (V)_{ij}, if j ≠ k.

Then D = αU + βV, where α and β are real numbers.

Since det(Λ_{1}^{u}) = det(Y_{1}^{u}), we can use the above remark repeatedly to write det(Λ_{1}^{u}) as a linear combination of the determinants det(C_{1}^{v}), where each C_{1}^{v} is the matrix obtained from C, after deleting the vth row and first column. Then it follows from (6.11) that

det(Λ_{1}^{u}) = ∑_{t=0}^{m−u}(−1)^{t}E(m, t) det(C_{1}^{u+t}) = ∑_{t=0}^{m+t}(−1)^{t}\binom{m + t}{t} det(C_{1}^{u+t}).  (6.14)

Each determinant det(C_{1}^{v}) can be evaluated by reduction to a Vandermonde determinant.

det(C_{1}^{v}) = \frac{n^{(m−1)(m−2)/2}}{2!3! ⋯ m!} ∏_{1≤s≤m, s≠v} sn(sn + 1)V (1, 2, …, v − 1, v + 1, …, m).

Now use the relation V (1, 2, …, v − 1, v + 1, …, m) = \frac{1!2! ⋯ (m − 1)!}{(v − 1)!(m − v)!}, to obtain

det(C_{1}^{v}) = \frac{n^{m(m−1)/2}}{m!} \binom{m}{v} ∏_{1≤s≤m, s≠v}(sn + 1).  (6.15)

Substituting for (6.15) in (6.14) gives

det(Λ_{1}^{v}) = \frac{n^{m(m−1)/2}}{m!} ∏_{s=1}^{m}(sn + 1) ∑_{t=0}^{m−u}(−1)^{t}\binom{m + t}{t}\frac{\binom{m}{u+t}}{((u + t)n + 1)}.  (6.16)

Lastly we eliminate the summation symbol by transformation into hypergeometric notation. As before we have

∑_{t=0}^{m−u}(−1)^{t}\binom{m + t}{t}\frac{\binom{m}{u+t}}{((u + t)n + 1)} = \frac{\binom{m}{u}}{un + 1}_{3}F_{2} ( \begin{matrix}m + 1, −m + u, \frac{1}{n}(nu + 1) \\ & , 1 \\ u + 1, \frac{1}{n}(nu + n + 1) \end{matrix} ) .

The Pfaff-Saalschultz Theorem applies again and we obtain, after routine simplifications,

∑_{t=0}^{m−u}(−1)^{t}\binom{m + t}{t}\frac{\binom{m}{u+t}}{((u + t)n + 1)}

= \frac{\binom{m}{u}}{un + 1} · \frac{(−m + u)_{m−u} (\frac{n−1}{n})_{m−u}}{(u + 1)_{m−u} (\frac{−nm−1}{b})_{m−u}} = \frac{∏_{k=1}^{m−u}(kn − 1)}{∏_{p=u}^{m}(pn + 1)}.

Substituting the last result into (6.16) gives the Lemma. □ Acknowledgement The author is grateful to his advisor, George E. Andrews, who is responsible for inventing q-partial fractions.

References

[1] G.E. Andrews. Applications of basic hypergeometric functions. SIAM Review, 16:441–484, 1974.

[2] G.E. Andrews. Partitions: At the interface of q-Series and Modular Forms. Ramanujan Journal 7 (1, 2, 3):385–400, 2003.

[3] G.E. Andrews. q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra. Volume 66 of CBMS Regional Conference Series in Mathematics, Published for the Conference Board of the Mathematical Sciences, Washington, D. C., 1986.

[4] G.E. Andrews. The Theory of Partitions. Addison-Wesley, Reading, 1976; reprinted by Cambridge University Press, Cambridge in 1984, 1998.

[5] G.E. Andrews, R. Askey and R. Roy. Special Functions. Cambridge University Press 1999.

[6] J. Arkin. Researches on Partitions. Duke Math. J., 38:403–409, 1970.

[7] A. Bjorner and R.P. Stanley. A Combinatorial Miscellany. L’Enseignement Math. (to appear).

[8] A. Cayley. Researches in the Partition of Numbers. Collected Math. Papers, 2:2 35–249, 506–512, 1898.

[9] G. Gasper and M. Rahman. Basic Hypergeometric Series. Cambridge University Press 1990.

[10] H. Gupter, M.M. Gwyther and J.C.P. Miller. Tables of Partitions. Royal Soc. Math. Tables, Vol. 4, Cambridge Univ Press, Cambridge, 1958.

[11] M.D. Hirschhorn, Triangles with Integer Sides Revisited. Math. Mag., 73:53-56, 2000.

[12] P.A. MacMahon. Combinatory Analysis. Vol. 2, Cambridge Univ. Press, Cambridge 1916; reprinted by Chelsea, New York in 1960.

[13] A.O. Munagi. The Rademacher Conjecture and q-Partial Fractions. Ramanujan Journal (to appear).

[14] V.V. Prasolov. Problems and Theorems in Linear Algebra. Translations of Mathematical Monographs, Vol. 134, AMS, Providence, 1994.

[15] H. Rademacher. Topics in Analytic Number Theory. Springer, New York, 1973.

[16] E.W. Weisstein. “Cyclotomic Polynomial” From MathWorld–A Wolfram Web Resource. ¡http://mathworld.wolfram.com/ CyclotomicPolynomial.html¿.

[17] H. Wilf. A Combinatorial Determinant. Eprint arXiv:math.CO/9809120, 09/1998.