Sums of Squares, Triangular Numbers, and Divisor Sums

G. E. Andrews^{1} Department of Mathematics Pennsylvania State University University Park, PA 16802

USA

 ea1@psu.edu

Sumit Kumar Jha 310, CS-Luxurio

Gachibowli Hyderabad

India

sumitkumarjha.iiit@gmail.com

J. López-Bonilla ESIME-Zacatenco

Instituto Politécnico Nacional Edif. 4, 1er. Piso

Col. Lindavista 07738 Ciudad de México

Mexico

jlopezb@ipn.mx

Abstract

We prove a general theorem that can be used to derive recurrences for familiar arithmetic functions such as r_{k}(n) and t_{k}(n), the number of representations of n as a sum of k squares and k triangular numbers, respectively.

1Author is partially supported by Simons Foundation Grant 633284.

1 Introduction

Jacobi first investigated the relationship between the sum of squares and divisor sums. Legendre also found formulas relating the sum of triangular numbers to divisor sums. The history of developments in this area has been covered by Dickson [2, Chaps. VI–IX]. More recent treatments include Grosswald [4] and Moreno-Wagstaff [3].

In this paper, we prove a general theorem that gives a number of recurrences, including the following:

r_{k}(n) = \frac{−2k}{n} ∑_{j=1}^{n}(−1)^{j} j D(j) r_{k}(n − j),  n ≥ 1  (1)

where r_{k}(n) denotes the number of representations of a positive integer n as a sum of k squares, and D(n) gives the sum of the reciprocals of the odd divisors of n.

We also prove that

t_{k}(n) = \frac{−k}{n} ∑_{j=1}^{n} j T (j) t_{k}(n − j),  (2)

where t_{k}(n) is the number of representations of n as the sum of k triangular numbers, representations with different orders are counted as unique, and

T (j) = ∑_{d|j} \frac{1 + 2 (−1)^{d}}{d} = \frac{1}{j} ∑_{d|j}(−1)^{d} d.  (3)

We state and prove our main theorem in Section 2. Section 3 is devoted to three special cases of this theorem.

2 The main theorem

Theorem 1. Let F (q) and G(q) be two analytic functions of q for |q| < 1 with F (0) = 1 and G(0) = 0. Further, let

q \frac{d}{dq} log F (q) = G(q),  (F (q))^{k} = ∑_{n=0}^{∞} f_{k}(n) q^{n},  G(q) = ∑_{n=1}^{∞} g_{n} q^{n}.

Then

f_{k}(n) = \frac{k}{n} ∑_{j=1}^{n} g_{j} f_{k}(n − j),  (4)

g_{n} = −n ∑_{k=1}^{n} \frac{(−1)^{k}}{k} \binom{n}{k} f_{k}(n).  (5)

Proof. From the hypotheses it is clear that f_{k}(0) = 1, for k ≥ 0, f_{0}(n) = δ_{0n} (δ_{ij} denotes the Kronecker delta), and g_{0} = 0. Furthermore, we have

q \frac{d}{dq} (F (q))^{k} = ∑_{n=0}^{∞} n f_{k}(n) q^{n}

= k (F (q))^{k} G(q)

= k (∑_{j=0}^{∞} f_{k}(j) q^{j}) (∑_{l=0}^{∞} g_{l} q^{l})

= k ∑_{n=0}^{∞} (∑_{j=1}^{n} g_{j} f_{k}(n − j)) q^{n},

which on comparison of coefficients of q^{n} on both the sides gives (4).

To prove (5), we use the generating function for the incomplete exponential Bell polynomials [1, p. 133] to deduce that

k! ∑_{n=k}^{∞} B_{n,k} (F′(0), F′′(0), …, F^{(n−k+1)}(0)) \frac{q^{n}}{n!} = (∑_{j=1}^{∞} F^{(j)}(0) \frac{q^{j}}{j} )^{k}

= (F (q) − 1)^{k}

= ∑_{m=0}^{k} \binom{k}{m} (−1)^{k−m} (F (q))^{m}

= ∑_{m=0}^{k} \binom{k}{m} (−1)^{k−m} ∑_{n=0}^{∞} f_{m}(n) q^{n}

which on comparison of coefficients of q^{n} on both the sides gives

B_{n,k} (F′(0), F′′(0), …, F^{(n−k+1)}(0)) = \frac{n!}{k!} ∑_{m=0}^{k}(−1)^{k−m} \binom{k}{m} f_{m}(n).  (6)

Now we use Faà di Bruno’s formula [5]:

\frac{d^{n}}{dq^{n}} Q(F (q)) = ∑_{k=1}^{n} Q^{(k)} (F (q)) B_{n,k} (F′(q), F′′(q), …, F^{(n−k+1)}(q))

with Q(q) = log q and let q → 0 to deduce that

\frac{−1}{n}g_{n} = \frac{1}{n!} ∑_{k=1}^{n}(−1)^{k} (k − 1)! B_{n,k} (F′(0), F′′(0), …, F^{(n−k+1)}(0))

= \frac{1}{n!} ∑_{k=1}^{n}(−1)^{k} (k − 1)! \frac{n!}{k!} ∑_{m=0}^{k}(−1)^{k−m} \binom{k}{m} f_{m}(n) (using (6))

= ∑_{k=1}^{n} \frac{(−1)^{k}}{k} ∑_{m=1}^{k}(−1)^{k−m} \binom{k}{m} f_{m}(n)

= ∑_{m=1}^{n}(−1)^{m} f_{m}(n) ∑_{k=m}^{n} \frac{1}{k} \binom{k}{m}

= ∑_{m=1}^{n}(−1)^{m} f_{m}(n) \frac{1}{m}\binom{n}{m},

where in the last step we have used the known “hockey stick” identity [7, 6]

∑_{k=m}^{n} \frac{1}{k} \binom{k}{m} = \frac{1}{m}\binom{n}{m}.

This completes our proof.

3 Three applications of the theorem

Corollary 2. We have

r_{k}(n) = \frac{−2k}{n} ∑_{j=1}^{n}(−1)^{j} j D(j) r_{k}(n − j) (n ≥ 1), (7)

and

D(n) = \frac{1}{n} ∑_{k=1}^{n} \frac{(−1)^{n−k}}{k} \binom{n}{k} r_{k}(n),  (8)

where D(n) is the sum of the inverses of the odd divisors of n, that is, D(n) = ∑_{{d|n \atop d odd}} \frac{1}{d}. Remark 3. Equation (8) was obtained by Jha [14]. Proof. In Theorem 1, we let

F (q) = ∑_{n=−∞}^{∞}(−1)^{n} q^{n^{2}} = ∏_{n=1}^{∞} \frac{1 − q^{n}}{1 + q^{n}} [8, Eq. (2.2.12) on p. 23].

Then f_{k}(n) = (−1)^{n} r_{k}(n). We can also deduce that

log F (q) = ∑_{j=1}^{∞} log(1 − q^{j}) − ∑_{j=1}^{∞} log(1 + q^{j})

= − ∑_{j=1}^{∞} ∑_{l=1}^{∞} \frac{q^{lj}}{l} + ∑_{j′=1}^{∞} ∑_{l′=1}^{∞} \frac{q^{l′j′}(−1)^{l′}}{l′}

= − ∑_{n=1}^{∞} q^{n} (∑_{d|n} \frac{1 − (−1)^{d}}{d} )

= −2 ∑_{n=1}^{∞} D(n) q^{n}.

Now using (4) and (5) we get (7) and (8), respectively. Corollary 4. We have

t_{k}(n) = \frac{−k}{n} ∑_{j=1}^{n} j T (j) t_{k}(n − j),  (9)

and

T (n) = ∑_{k=1}^{n} \frac{(−1)^{k}}{k} \binom{n}{k} t_{k}(n),  (10)

where T (n) is given by (3). Proof. In Theorem 1, we let

F (q) = ∑_{n=0}^{∞} q^{\frac{(n)(n+1)}{2}} = ∏_{j=1}^{∞} \frac{(1 − q^{2j})^{2}}{(1 − q^{j})} = ∏_{j=1}^{∞}(1 + q^{j})^{2} (1 − q^{j}) [8, Eq. (2.2.13) on p. 23].

Then

f_{k}(n) = t_{k}(n).

We can also deduce that

log(F (q)) = ∑_{j=1}^{∞} 2 log(1 + q^{j}) + ∑_{j=1}^{∞} log(1 − q^{j})

= − ∑_{j=1}^{∞} ∑_{l=1}^{∞} 2 \frac{(−1)^{l} q^{lj}}{l} − ∑_{j′=1}^{∞} ∑_{l′=1}^{∞} \frac{q^{l′j′}}{l′}

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

Now using (4) and (5) we get (7) and (8), respectively.

Remark 5. Robbins [9] has shown the relation

∑_{{d|n \atop d odd}} d = n ∑_{d|n} \frac{(−1)^{d−1}}{d} .  (11)

This implies the second equality in (3).

Corollary 6. Let ∏_{n≥1}(1 − q^{n})^{k} = ∑_{n=0}^{∞} p_{k}(n) q^{n}. Then we have

p_{k}(n) = \frac{−k}{n} ∑_{j=1}^{n} σ(j) p_{k}(n − j),  (12)

and

σ(n) = n ∑_{k=1}^{n} \frac{(−1)^{k}}{k} \binom{n}{k} p_{k}(n),  (13)

where σ(n) = ∑_{d|n} d.

Remark 7. Equation (12) was first obtained by Gandhi [11, 12]. Equation (13) was obtained by Jha [13].

Proof. In Theorem 1, we let

F (q) = ∏_{n≥1}(1 − q^{n}) = ∑_{n=−∞}^{∞}(−1)^{n}q^{\frac{3n^{2}+n}{2}} .

Then f_{k}(n) = p_{k}(n), which denotes the number of partitions of n with k colors. We can also deduce that

log(F (q)) = ∑_{j=1}^{∞} log(1 − q^{j})

= − ∑_{j=1}^{∞} ∑_{l=1}^{∞} \frac{q^{lj}}{l}

= − ∑_{n=1}^{∞} q^{n} (∑_{d|n} \frac{1}{d})

= − ∑_{n=1}^{∞} \frac{σ(n) q^{n}}{n} .

Now using (4) and (5) we get (12) and (13), respectively.

Remark 8. Letting k = −1 in the equation (12) gives the well-known relation:

n p(n) = ∑_{j=1}^{n} σ(j) p_{k}(n − j).

Furthermore, letting k = 1 gives an identity obtained by Osler-Hassen-Chandrupatla [10]

σ(n) = −n a_{n} − ∑_{j=1}^{n−1} σ(j) a_{n−j} (n ≥ 2),

where

a_{j} = \begin{cases}0, & if j ≠ \frac{N}{2} (3N + 1); \\ (−1)^{N}, & if j = \frac{N}{2} (3N + 1). \end{cases}

Here N = 0, ±1, ±2, . . ..

References

[1] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Springer, 2011.

[2] L. E. Dickson, History of the Theory of Numbers. Vol. II: Diophantine Analysis, Dover Publications, 2005.

[3] C. J. Moreno and S. S. Wagstaff Jr., Sums of Squares of Integers, Chapman & Hall/CRC, 2006.

[4] E. Grosswald, Topics from the Theory of Numbers, Birkäuser, 1984.

[5] W. P. Johnson, The curious history of Faà di Bruno’s formula, Amer. Math. Monthly 109 (2002), 217–234.

[6] C. H. Jones, Generalized hockey stick identities and N-dimensional block walking, Fibonacci Quart. 34 (1996), 280–288.

[7] T. Arakawa, T. Ibukiyama, and M. Kaneko, Bernoulli numbers and Zeta Functions, Springer, 2014.

[8] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1998.

[9] N. Robbins, On partition functions and divisor sums, J. Integer Sequences 5 (2002), Article 02.1.4.

[10] T. J. Osler, A. Hassen, and T. R. Chandrupatla, Surprising connections between partitions and divisors, College Math. J. 38 (2007), 278–287.

[11] J. M. Gandhi, Congruences for p_{r}(n) and Ramanujan’s τ-function, Amer. Math. Monthly 70 (1963), 265–274.

[12] O. Lazarev, M. Mizuhara, and B. Reid, Some results in partitions, plane partitions, and multipartitions, Summer 2010 REU program in mathematics at Oregon State University, 2010.

[13] S. Kumar Jha, A combinatorial identity for the sum of divisors function involving p_{r}(n), Integers 20 (2020), Paper #A97.

[14] S. Kumar Jha, An identity for the sum of inverses of odd divisors of n in terms of the number of representations of n as a sum of squares, Rocky Mountain J. Math. 51 (2021) 581–583.

2020 Mathematics Subject Classification: Primary 11A99, Secondary 11P99. Keywords: sum of divisors function, colour partition, sum of inverses of odd divisors of an integer, triangular number, sum of squares.

(Concerned with sequences \underline{A000041} and \underline{A000118}.)

Received October 15 2022; revised versions received October 16 2022; February 9 2023; February 12 2023; February 25 2023. Published in Journal of Integer Sequences, February 25 2023.

Return to Journal of Integer Sequences home page.