5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What is the asymptotic limit that you are trying to analyse? Is it $n\to\infty$ or is it $k\to\infty$? Could you please specify what is the meaning of the notation $\sum_{d|i}$? Also, do you know anything about $\phi(x)$? $\endgroup$ Mar 21, 2018 at 15:57
  • 1
    $\begingroup$ @AlekseyPichugin I edited the post to include those things. $\endgroup$ Mar 21, 2018 at 16:45

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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