It’s fairly well-known, to those who know it, that
In other words, the square of the sum of the first n positive integers equals the sum of the cubes of the first n positive integers.
It’s probably less well-known that a similar relationship holds for , the function that counts the number of divisors of an integer:
In this post we’re going to prove this formula for .
First, it’s pretty easy to see what the value of is for prime powers; i.e., integers of the form , where p is prime. Since the only divisors of are , the number of divisors of is given by .
Let’s check the identity we’re trying to prove when . We have
We also have
Clearly, the two expressions are equal, so the identity we’re trying to prove holds in the prime-power case. (And, in fact, the derivation uses the identity about the sum of the first several positive integers mentioned at the beginning of the post!)
Let and . What we’ve shown thus far is that .
Now, we’re going to pull some elementary number theory. One fact about is that it is multiplicative; i.e., when m and n are relatively prime. This is one of the first properties you learn about once you learn its definition, and we’re not going to prove it here.
It turns out that both f and F are multiplicative as well! First, the product of two multiplicative functions is also multiplicative. (This is a one-line proof using the definition of multiplicative.) So is multiplicative.
Another property of multiplicative functions is that if g is multiplicative, then is also multiplicative. This is a special case of the more general result that the Dirichlet convolution of two multiplicative functions is multiplicative. (In the Dirichlet convolution , take h to be the identity function; i.e., .) This means that our functions f and F defined in the previous paragraph are both multiplicative.
Therefore, with the prime-power factorization of n given by , we have
For an even further generalization, see Barbeau and Seraj . (The proof we give in this post follows the same basic argument as the proof of Proposition 1 in Barbeau and Seraj’s paper.)
- Barbeau, Edward, and Samer Seraj, “Sum of cubes is square of sum,” Notes on Number Theory and Discrete Mathematics 19(1), 2013, pages 1–13.