Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here's a question I've been asked:

Let $n\in \mathbb{N}$ and let $d_k(n)$ be the number of solutions of $$x_1\dots x_k = n, \hspace{5mm}x_i\in \mathbb{N}$$

I need to show

$$d_k(n) = \sum_{d|n}d_{k-1}(d), \hspace{5mm} k \ge 2$$ and that for any $\epsilon > 0$, $d_k(n) = O(n^\epsilon)$ where the implied constant depends only on $k$. I.e $d_k(n) \ll f(k)n^\epsilon$ for some function $f$.

I have to admit, I'm lacking an idea of what $d_k(n)$ looks like. Setting up the base case for an inductive argument isn't difficult, but I'm having a hard time picturing how this being true for an arbitrary $k$ implies the statement for $k+1$. The statement $\epsilon > 0$, $d_k(n) = O(n^\epsilon)$ is also very strange to me, having a CS background. I can kind of see how the choice of $\epsilon$ is arbitrary, since it just varies the implied constant in $O(n^\epsilon$). I can't seem to reconcile any of this in my head. Advice? Thanks for your time.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

For the summation, note that $d_k(n)$ is the number of ordered $k$-tuples $(x_1,x_2, \dots, x_k)$ of $x_2x_2\cdots x_k=n$.

If $d$ is any divisor of $n$, consider the $k$-tuples whose last term $x_k$ is equal to $n/d$. How many of these are there? The $(k-1)$-tuple $(x_1,x_2,\dots, x_{k-1})$ must then have product $d$, and by definition there are $d_{k-1}(d)$ such $(k-1)$-uples. Finally, sum over all $d$ that divide $n$.

For the estimate, probably you are expected to use the just proved sum result, and to use an upper bound on the number of divisors of $n$ to bound $d_k(n)$.

Remark: If you are familiar with the term, note that the relationship just proved shows that $d_k(n)$ is multiplicative, that is, that $d_k(ab)=d_k(a)d_k(b)$ whenever $a$ and $b$ are relatively prime.

That implies that we can write down $d_k(n)$ once we know the structure of the prime power factorization of $n$.

share|improve this answer
Ahh great idea about it being multiplicative. Things like that are never apparent to me... thought I'm slowly getting better. Thanks for the reply! –  user45814 Nov 19 '12 at 4:01
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.