[proofplan] We prove the result by induction on $k$, using the convolution identity $d_k = d_{k-1} * 1$. The summatory function of $d_k$ is therefore obtained by summing the summatory function of $d_{k-1}$ over the dilates $x/m$. The main term is reduced to asymptotics for harmonic sums of powers of $\log(x/m)$, and the error term is controlled by splitting the summation range into a region where the induction hypothesis is uniform and a short terminal region handled by a crude divisor bound. [/proofplan] [step:Establish the base case $k=1$] For $k=1$, the definition gives $d_1(n)=1$ for every $n \in \mathbb{N}$. Hence \begin{align*} \sum_{1 \leq n \leq x} d_1(n) = \lfloor x \rfloor = x + O(1) = x + o(x) \end{align*} as $x \to \infty$. Thus the assertion holds with the constant polynomial $P_0(T)=1$, whose leading coefficient is $1=1/0!$. [/step] [step:Record the harmonic sum asymptotic needed for the induction] Fix an integer $j \geq 0$. Let $\mathcal{L}^1$ denote one-dimensional Lebesgue measure, and for a real-valued function $g: [1,x] \to \mathbb{R}$ of bounded variation let $\operatorname{Var}_{[1,x]}(g)$ denote its total variation on $[1,x]$. Define the harmonic-sum function \begin{align*} H_j : [1,\infty) &\to \mathbb{R} \\ y &\mapsto \sum_{1 \leq m \leq y} \frac{(\log(y/m))^j}{m}. \end{align*} Then \begin{align*} H_j(x) = \frac{(\log x)^{j+1}}{j+1} + O\left((\log x)^j\right) \end{align*} as $x \to \infty$. Indeed, for each real $x \geq 1$, the function \begin{align*} f_x : [1,x] &\to \mathbb{R} \\ t &\mapsto \frac{(\log(x/t))^j}{t} \end{align*} is non-negative and monotone up to a bounded number of monotonicity changes depending only on $j$. The integral comparison for [functions of bounded variation](/page/Functions%20of%20Bounded%20Variation) gives \begin{align*} \sum_{1 \leq m \leq x} f_x(m) = \int_1^x f_x(t)\,d\mathcal{L}^1(t) + O\left(\sup_{1 \leq t \leq x} f_x(t)+\operatorname{Var}_{[1,x]}(f_x)\right). \end{align*} The error is $O((\log x)^j)$. With the substitution $u=\log(x/t)$, so that $d\mathcal{L}^1(t)/t=-d\mathcal{L}^1(u)$ and $t=1$ corresponds to $u=\log x$ while $t=x$ corresponds to $u=0$, the integral equals \begin{align*} \int_1^x \frac{(\log(x/t))^j}{t}\,d\mathcal{L}^1(t) = \int_0^{\log x} u^j\,d\mathcal{L}^1(u) = \frac{(\log x)^{j+1}}{j+1}. \end{align*} This proves the stated asymptotic for $H_j(x)$. [guided] We need to understand sums of the form \begin{align*} \sum_{1 \leq m \leq x} \frac{(\log(x/m))^j}{m}, \end{align*} because the induction step will substitute the asymptotic formula for the summatory function of $d_{k-1}$ at the point $x/m$. Fix $j \geq 0$. Let $\mathcal{L}^1$ denote one-dimensional Lebesgue measure. Define the harmonic-sum function \begin{align*} H_j : [1,\infty) &\to \mathbb{R} \\ y &\mapsto \sum_{1 \leq m \leq y} \frac{(\log(y/m))^j}{m}. \end{align*} The corresponding integral is \begin{align*} \int_1^x \frac{(\log(x/t))^j}{t}\,d\mathcal{L}^1(t). \end{align*} Use the substitution $u=\log(x/t)$. Then $d\mathcal{L}^1(t)/t=-d\mathcal{L}^1(u)$, the lower endpoint $t=1$ becomes $u=\log x$, and the upper endpoint $t=x$ becomes $u=0$. Therefore \begin{align*} \int_1^x \frac{(\log(x/t))^j}{t}\,d\mathcal{L}^1(t) = \int_0^{\log x} u^j\,d\mathcal{L}^1(u) = \frac{(\log x)^{j+1}}{j+1}. \end{align*} It remains to justify replacing the sum by the integral with a lower-order error. For a real-valued function $g: [1,x] \to \mathbb{R}$ of bounded variation, let $\operatorname{Var}_{[1,x]}(g)$ denote its total variation on $[1,x]$. The function \begin{align*} f_x : [1,x] &\to \mathbb{R} \\ t &\mapsto \frac{(\log(x/t))^j}{t} \end{align*} has only a bounded number of monotonicity intervals depending on $j$, and $\operatorname{Var}_{[1,x]}(f_x)=O((\log x)^j)$. The standard integral comparison on each monotonicity interval gives \begin{align*} H_j(x) = \int_1^x f_x(t)\,d\mathcal{L}^1(t) + O\left((\log x)^j\right). \end{align*} Combining this with the explicit integral evaluation gives \begin{align*} H_j(x) = \frac{(\log x)^{j+1}}{j+1} + O\left((\log x)^j\right). \end{align*} [/guided] [/step] [step:Prove a crude divisor summatory bound for later error control] For each fixed integer $r \geq 1$, there is a constant $C_r>0$ such that \begin{align*} \sum_{1 \leq n \leq y} d_r(n) \leq C_r y(1+\log y)^{r-1} \end{align*} for all real $y \geq 1$. The case $r=1$ follows from $\lfloor y \rfloor \leq y$. Suppose the estimate holds for $r-1$. Since every ordered $r$-fold factorization of $n$ is obtained by choosing its last factor $m$ and then an ordered $(r-1)$-fold factorization of $n/m$, we have \begin{align*} d_r(n)=\sum_{m \mid n} d_{r-1}(n/m). \end{align*} Hence, for $y \geq 1$, \begin{align*} \sum_{1 \leq n \leq y} d_r(n) &= \sum_{1 \leq m \leq y} \sum_{1 \leq a \leq y/m} d_{r-1}(a) \\ &\leq C_{r-1}\sum_{1 \leq m \leq y} \frac{y}{m}\left(1+\log(y/m)\right)^{r-2}. \end{align*} The harmonic sum estimate from the previous step, applied to each power appearing after expanding $\left(1+\log(y/m)\right)^{r-2}$, gives \begin{align*} \sum_{1 \leq m \leq y} \frac{\left(1+\log(y/m)\right)^{r-2}}{m} \leq C'_r(1+\log y)^{r-1} \end{align*} for a constant $C'_r>0$. Thus the desired bound holds with $C_r=C_{r-1}C'_r$. [/step] [step:Express the $k$th summatory function through the $(k-1)$st summatory function] Assume the theorem holds for $k-1$, where $k \geq 2$. Define the summatory functions \begin{align*} D_r : [1,\infty) &\to \mathbb{R} \\ y &\mapsto \sum_{1 \leq n \leq y} d_r(n) \end{align*} for integers $r \geq 1$. The convolution identity \begin{align*} d_k(n)=\sum_{m \mid n} d_{k-1}(n/m) \end{align*} gives \begin{align*} D_k(x) &= \sum_{1 \leq n \leq x} \sum_{m \mid n} d_{k-1}(n/m) \\ &= \sum_{1 \leq m \leq x} \sum_{1 \leq a \leq x/m} d_{k-1}(a) \\ &= \sum_{1 \leq m \leq x} D_{k-1}(x/m). \end{align*} By the induction hypothesis, there is a polynomial $Q_{k-2} \in \mathbb{R}[T]$ of degree $k-2$ with leading coefficient $1/(k-2)!$ such that \begin{align*} D_{k-1}(y) = y Q_{k-2}(\log y) + o\left(y(\log y)^{k-2}\right). \end{align*} [/step] [step:Sum the inductive main term and identify the new leading coefficient] Write \begin{align*} Q_{k-2}(T)=\sum_{j=0}^{k-2} a_j T^j, \end{align*} where $a_{k-2}=1/(k-2)!$. Define the main-term function \begin{align*} M_k : [1,\infty) &\to \mathbb{R} \\ x &\mapsto \sum_{1 \leq m \leq x} \frac{x}{m} Q_{k-2}(\log(x/m)). \end{align*} Expanding $Q_{k-2}$ gives \begin{align*} M_k(x) &= x \sum_{j=0}^{k-2} a_j \sum_{1 \leq m \leq x} \frac{(\log(x/m))^j}{m}. \end{align*} Using the harmonic sum asymptotic for each $j$, we obtain \begin{align*} M_k(x) = x \sum_{j=0}^{k-2} a_j \frac{(\log x)^{j+1}}{j+1} + O\left(x(\log x)^{k-2}\right). \end{align*} Define \begin{align*} P_{k-1}(T) := \sum_{j=0}^{k-2} \frac{a_j}{j+1}T^{j+1}. \end{align*} Then $P_{k-1}$ has degree $k-1$, and its leading coefficient is \begin{align*} \frac{a_{k-2}}{k-1} = \frac{1}{(k-2)!(k-1)} = \frac{1}{(k-1)!}. \end{align*} Therefore \begin{align*} M_k(x) = xP_{k-1}(\log x) + O\left(x(\log x)^{k-2}\right). \end{align*} [guided] The induction hypothesis gives the main term for $D_{k-1}(y)$ as $yQ_{k-2}(\log y)$. In the identity \begin{align*} D_k(x)=\sum_{1 \leq m \leq x}D_{k-1}(x/m), \end{align*} this main term becomes the function \begin{align*} M_k : [1,\infty) &\to \mathbb{R} \\ x &\mapsto \sum_{1 \leq m \leq x} \frac{x}{m}Q_{k-2}(\log(x/m)). \end{align*} Write the polynomial $Q_{k-2}$ explicitly as \begin{align*} Q_{k-2}(T)=\sum_{j=0}^{k-2} a_jT^j, \end{align*} where the induction hypothesis says $a_{k-2}=1/(k-2)!$. Substituting this expansion into $M_k(x)$ gives \begin{align*} M_k(x) = x\sum_{j=0}^{k-2}a_j \sum_{1 \leq m \leq x}\frac{(\log(x/m))^j}{m}. \end{align*} The harmonic sum estimate proved earlier gives, for each fixed $j$, \begin{align*} \sum_{1 \leq m \leq x}\frac{(\log(x/m))^j}{m} = \frac{(\log x)^{j+1}}{j+1} + O\left((\log x)^j\right). \end{align*} Therefore \begin{align*} M_k(x) = x\sum_{j=0}^{k-2}\frac{a_j}{j+1}(\log x)^{j+1} + O\left(x(\log x)^{k-2}\right). \end{align*} This naturally defines the next polynomial: \begin{align*} P_{k-1}(T) := \sum_{j=0}^{k-2}\frac{a_j}{j+1}T^{j+1}. \end{align*} The highest power comes from $j=k-2$, so the coefficient of $T^{k-1}$ is \begin{align*} \frac{a_{k-2}}{k-1} = \frac{1}{(k-2)!(k-1)} = \frac{1}{(k-1)!}. \end{align*} Thus the main term has precisely the required polynomial shape: \begin{align*} M_k(x) = xP_{k-1}(\log x) + O\left(x(\log x)^{k-2}\right). \end{align*} [/guided] [/step] [step:Show that the summed induction error is lower order] Let \begin{align*} R_{k-1} : [1,\infty) &\to \mathbb{R} \\ y &\mapsto D_{k-1}(y)-yQ_{k-2}(\log y) \end{align*} be the induction error. Then \begin{align*} R_{k-1}(y)=o\left(y(\log y)^{k-2}\right) \end{align*} as $y \to \infty$. We prove \begin{align*} \sum_{1 \leq m \leq x} R_{k-1}(x/m) = o\left(x(\log x)^{k-1}\right). \end{align*} Fix $\varepsilon>0$. By the definition of little-$o$, choose $Y_\varepsilon \geq 2$ such that \begin{align*} |R_{k-1}(y)| \leq \varepsilon y(\log y)^{k-2} \end{align*} for all $y \geq Y_\varepsilon$. Split the sum into \begin{align*} S_1(x) &:= \sum_{1 \leq m \leq x/Y_\varepsilon} R_{k-1}(x/m), \\ S_2(x) &:= \sum_{x/Y_\varepsilon < m \leq x} R_{k-1}(x/m). \end{align*} For $S_1(x)$, the bound above gives \begin{align*} |S_1(x)| &\leq \varepsilon x \sum_{1 \leq m \leq x/Y_\varepsilon} \frac{(\log(x/m))^{k-2}}{m} \\ &\leq C_k\varepsilon x(\log x)^{k-1} \end{align*} for a constant $C_k>0$ depending only on $k$, by the harmonic sum estimate. For $S_2(x)$, the crude divisor bound and the polynomial growth of $Q_{k-2}$ give a constant $A_k>0$ such that \begin{align*} |R_{k-1}(y)| \leq A_k y(1+\log y)^{k-2} \end{align*} for all $y \geq 1$. Hence \begin{align*} |S_2(x)| &\leq A_k x \sum_{x/Y_\varepsilon < m \leq x} \frac{(1+\log(x/m))^{k-2}}{m}. \end{align*} Since $x/Y_\varepsilon < m \leq x$ implies $1 \leq x/m < Y_\varepsilon$, the last sum is \begin{align*} O_{k,Y_\varepsilon}(1). \end{align*} Thus \begin{align*} |S_2(x)|=O_{k,Y_\varepsilon}(x) = o\left(x(\log x)^{k-1}\right). \end{align*} Combining the two estimates gives \begin{align*} \limsup_{x \to \infty} \frac{\left|\sum_{1 \leq m \leq x} R_{k-1}(x/m)\right|} {x(\log x)^{k-1}} \leq C_k\varepsilon. \end{align*} Since $\varepsilon>0$ was arbitrary, the summed error is $o(x(\log x)^{k-1})$. [/step] [step:Combine the main term and error estimates to complete the induction] From the decomposition \begin{align*} D_k(x) = \sum_{1 \leq m \leq x} D_{k-1}(x/m) = M_k(x) + \sum_{1 \leq m \leq x} R_{k-1}(x/m), \end{align*} the previous two steps give \begin{align*} D_k(x) = xP_{k-1}(\log x) + O\left(x(\log x)^{k-2}\right) + o\left(x(\log x)^{k-1}\right). \end{align*} Since \begin{align*} O\left(x(\log x)^{k-2}\right) = o\left(x(\log x)^{k-1}\right), \end{align*} we conclude that \begin{align*} \sum_{1 \leq n \leq x}d_k(n) = xP_{k-1}(\log x) + o\left(x(\log x)^{k-1}\right). \end{align*} The polynomial $P_{k-1}$ has degree $k-1$ and leading coefficient $1/(k-1)!$, as shown above. The induction is complete for every fixed integer $k \geq 1$. [/step]