Divisor function convolution

Question

I need some help to prove that $$ (d*d)(p^k) = \frac{(k+3)(k+2)(k+1)}{6} \qquad \forall p \in \mathcal{P},\quad \forall k \in \mathbb{N}, $$ where $d$ is the divisor function and $\mathcal{P}$ the set of primes.
Any ideas? Thank you in advance.

Answer 1

Let $f$ be the convolution of $d$ and $d$. Then $$f(n)=\sum_{i|n}d(i)d(n/i).$$ We need to find $f(p^k)$. The divisors of $p^t$ are $1,p,\dots,p^t$, so there are $t+1$ of them. And $\frac{p^k}{p^t}$ has $k-t+1$ divisors. It follows that $$f(p^k)=\sum_{t=0}^{k}(t+1)(k-t+1).$$ Note that $$(t+1)(k-t+1)=n(t+1)-t^2+1.$$ Now we can use standard summation formulas. The sum is $$k\cdot \frac{(k+1)(k+2)}{2}-\frac{k(k+1)(2k+1)}{6}+k+1.$$ Simplify. It is helpful to take out the common factor $k+1$.

Remark: This is a straightforward but ugly grinding approach. There is undoubtedly a nice combinatorial argument.

Answer 2

Using the fact that for any $p$ prime and integer $k$ we have $d(p^k)=k+1$:

$$d*d(p^k) = \sum_{i=0}^{k} d(p^i)d(p^{k-i})= \sum_{i=0}^{k} (i+1)(k-i+1) = k\sum_{i=0}^{k}(i+1) - \sum_{i=0}^{k} (i^2 -1)$$

Now for the first sum: $$k\sum_{i=0}^{k}(i+1) = k\frac{(k+2)(k+1)}{2}$$

For the second sum: $$ \sum_{i=0}^{k} (i^2 -1) = \sum_{i=0}^{k} i^2 - (k+1) $$

And it can be shown that $$\sum_{i=0}^{k} i^2 = \frac{n(n+1)(2n+1)}{6}$$

Sum it all up and you'll get the answer

Answer 3

we have, because the only divisors of $p^k$ are $p^i$ with $i$ between $0$ and $k$, $(d*d)(p^k) = \sum_{i=0}^k d(p^i)d(p^{k-i})=\sum_{i=0}^k (i+1)(k-i+1)$

Then you just have to develop to prove easily that $\sum_{i=0}^k (i+1)(k-i+1)= \frac{(k+3)(k+2)(k+1)}{6}$