Asymptotically analyzing a sum

Question

This sum popped out in some of the work I have been doing, and I have been trying to analyze it asymptotically as $n$ approaches infinity, $$S=k^n+\sum_{i=1}^n\frac{1}{i}\sum_{d|i}\phi(d) k^{i/d}.$$ In this equation $\phi(d)$ is the Euler totient function, and $\sum_{d|i}$ means we are summing over all divisors $d$ of $i$, and $k\in \mathbb{N}$.

Since $k^n$ is the largest term in $S$, we have $S=\Theta(k^n)$, but I want to do better since it doesn't really tell me how big the coefficient in front of $k^n$ is as $n$ goes to infinity. If we look at the double sum, we get $$\sum_{i=1}^n\frac{1}{i}\sum_{d|i}\phi(d) k^{i/d}\sim \sum_{i=1}^n\frac{1}{i}k^{i} = \Theta\bigg(\frac{k^n}{n}\bigg) $$ So can we say that $$S\sim k^n+\frac{k^n}{n} = \bigg(\frac{n+1}{n}k^n\bigg) = (1+o(1))k^n.$$ Is this right? It doesn't feel right doing that, but I don't know exactly what feels wrong.

Answer 1

Your conclusion is correct (assuming that $k$ is fixed), and your reasoning is basically correct as well.

Since the exponent on $k$ is the most important consideration for the sizes of the terms, let's sort the sum by that exponent: \begin{align*} S=k^n+\sum_{i=1}^n\frac{1}{i}\sum_{d|i}\phi(d) k^{i/d}&=k^n+\sum_{d=1}^n \frac{\phi(d)}d \sum_{\substack{1\le i\le n \\ d\mid i}} \frac di k^{i/d}\\ &=k^n+\sum_{d=1}^n \frac{\phi(d)}d \sum_{\substack{1\le i\le n \\ d\mid i}} \frac di k^{i/d}\\ &=k^n+\sum_{d=1}^n \frac{\phi(d)}d \sum_{\substack{1\le q\le n/d}} \frac {k^q}q\\ &=k^n+\sum_{q=1}^n \frac {k^q}q \sum_{\substack{1\le d\le n/q}} \frac{\phi(d)}d=\frac{n+1}nk^n +\sum_{q=1}^{n-1} \frac {k^q}q \sum_{\substack{1\le d\le n/q}} \frac{\phi(d)}d. \end{align*} The first term is asymptotic to $k^n$, as you observed. The terms in the sum with $n/2 < q \le n-1$ contribute at most $$ \sum_{n/2 < q \le n-1} \frac{k^q}q \cdot 1 \le \sum_{n/2 < q \le n-1} \frac{k^q}{n/2} < \frac2n \sum_{q=-\infty}^{n-1} k^q = \frac2n \frac{k^n}{k-1}, $$ while the remaining terms contribute $$ \sum_{1\le q\le n/2} \frac {k^q}q\sum_{1\le d\le n/q} \frac{\phi(d)}d \le \sum_{1\le q\le n/2} \frac {k^q}q \frac nq \le n \sum_{1\le q\le n/2} \frac {k^{n/2}}{q^2} < 2nk^{n/2}. $$ Both of these contributions are insignificant compared to the $k^n$ main term.