8
$\begingroup$

I have quite an interesting infinite totient sum. My task is to evaluate

$\sum_{n=1}^{\infty} \frac{\phi(n)}{5^n +1}.$

The problem is that I have no idea how to go from here as I have never seen such a problem before. The usual techique of writing $n$ and $\phi(n)$ in terms of the prime factorization of $n$ doesn't work. I get $\frac{\phi(n)}{5^n+1}=\frac{\prod_i p_i^{e_i-1} (p_i-1)}{5^{\prod p_i^{e_i}}+1}$, which turns into a complete crocodile when plugged back into the summation.

I know that the problem has an elegant, closed form solution because it appeared on a problem set that is expected to be solved by mere high school students. Furthermore, the only way to simplify such an infinite sum is to turn it into a numerical answer. Wolfram Alpha is unable to give a closed form solution, so I know that there is some clever trick to demolish this problem that I have not seen before. Does anyone have any hints or ideas on how do deal with this?

My only guess is that 5 is quite a peculiar number, and so it seems reasonable that the sum $\sum_{n=1}^{\infty} \frac{\phi(n)}{a^n +1}$ should also have a closed form solution for any integer $a$.

Update: Summing up to $n=1000$ using Wolfram-Alpha (it seems that my mistake was asking it to sum infinitely many terms) gives $0.22569444444444...$ with no end to the relentless onslaught of the 4's. Therefore I believe that the sum is $\frac{65}{288} = \frac{5 \cdot 13}{2^5 \cdot 3^2}.$ I have split up the possible answer into prime factors so that the clever trick I had earlier alluded to may be hopefully found. However, I do not have the luxury of pulling out a computational device on a math competition, and so I hope to find the actual solution, i.e. the method through one may derive this answer.

Update: We define $f(a) = \sum_{n=1}^{\infty} \frac{\phi(n)}{a^n +1}$. Here are some reasonable values for prime $a$ in case someone may try to use these to find the solution. At this point, I believe the only way to find a rigorous solution is to work backwards from the likely solution given by WA.

$f(2)=22569444444444...=\frac{5 \cdot 13}{2^5 3^2}$

$f(3)=0.$

$f(5)=0.$

$f(7)=0.$

$f(11)=0.09319444444...=\frac{11 \cdot 61}{2^5 3^2 5^2}$

Additional Update: With the help of achille hui, I have found that $$\sum_{n=1}^{\infty} \frac{\phi(n)}{1-(-1)^n q^n} = \frac{q}{(q+1)^2}.$$

This is almost the right sum.

$\endgroup$
  • 3
    $\begingroup$ Hint: $\sum_{n=1}^\infty \frac{\varphi(n)q^n}{1-q^n} = \frac{q}{(1-q)^2}$ for $|q| < 1$. $\endgroup$ – achille hui Feb 28 '18 at 4:34
  • $\begingroup$ @achillehui This is certainly useful, but I would like to know how to prove this identity as well. It appears to be a malformed, convoluted, and mangled geometric series, but that does not lead me any further to the proof of your lemma. $\endgroup$ – Display name Feb 28 '18 at 4:36
  • 2
    $\begingroup$ Start from the identity $\sum_{n|k} \varphi(n) = k$ by Gauss, one has $$\sum_{n=1}^\infty \frac{\varphi(n)q^n}{1-q^n} = \sum_{m=1}^\infty\sum_{n=1}^\infty \varphi(n)q^{nm} = \sum_{k=1}^\infty \left(\sum_{n|k}\varphi(n)\right) q^k = \sum_{k=1}^\infty kq^k = \frac{q}{(1-q)^2}$$ $\endgroup$ – achille hui Feb 28 '18 at 4:43
  • $\begingroup$ @achillehui Thank you for the nice and concise proof. I will now try solving the original problem I posed. By the way, how do you come up with these manipulations? The proof seems easy in hindsight, but there's no way I could've come up with this. $\endgroup$ – Display name Feb 28 '18 at 4:53
  • 1
    $\begingroup$ Look at the wiki entry of Euler's totient function. I originally only know the identity by Gauss and I notice the second identity for Lambert series. The wiki entry say it is trivial to prove by manipulating the definition. So I just prove it. $\endgroup$ – achille hui Feb 28 '18 at 4:57
8
$\begingroup$

Notice for any prime $p$ and integer $k \ge 0$, we have

$$\varphi(p^k) = \begin{cases}p^k - p^{k-1}, & k > 0\\ 1,& k = 0\end{cases} \quad\implies\quad \sum_{\ell=0}^k \varphi(p^\ell) = p^k $$ For any $n \in \mathbb{Z}_{+}$, if we factorize it into a product of primes $n = p_1^{e_1}\ldots p_m^{e_m}$, we can use above fact to deduce following identity by Gauss $$\begin{align}\sum_{d|n} \varphi(d) &= \sum_{\ell_1=0}^{e_1} \cdots\sum_{\ell_m=0}^{e_m} \varphi(p_1^{e_1} \cdots p_m^{e_m})= \sum_{\ell_1=0}^{e_1} \cdots\sum_{\ell_m=0}^{e_m} \varphi(p_1^{e_1}) \cdots \varphi(p_m^{e_m})\\ &= \prod_{i=1}^m \left(\sum_{\ell_i=0}^{e_i}\varphi(p_i^{e_i})\right) = \prod_{i=1}^m p_i^{e_i} = n \end{align} $$ As a result, for any $|q| < 1$, we have $$F(q) \stackrel{def}{=}\sum_{n=1}^\infty \frac{\varphi(n)q^n}{1-q^n} = \sum_{n=1}^\infty\sum_{m=1}^\infty \varphi(n)q^{nm} = \sum_{k=1}^\infty \left(\sum_{d|k} \varphi(d)\right) q^k = \sum_{k=1}^\infty k q^k = \frac{q}{(1-q)^2}$$

As a corollary, for any $|a| > 1$, we have

$$\sum_{n=1}^\infty \frac{\varphi(n)}{a^n-1} = \sum_{n=1}^\infty \frac{\varphi(n)a^{-n}}{1-a^{-n}} = F(a^{-1}) = \frac{a}{(a-1)^2}$$

This leads to

$$\sum_{n=1}^\infty \frac{\varphi(n)}{a^n+1} =\sum_{n=1}^\infty \varphi(n)\left(\frac{1}{a^n-1} - \frac{2}{a^{2n}-1}\right) = \frac{a}{(a-1)^2} - \frac{a^2}{(a^2-1)^2} = \frac{a(a^2+1)}{(a^2-1)^2} $$ Substitute $a = 5$, we get $$\sum_{n=1}^\infty \frac{\varphi(n)}{5^n+1} = \frac{5(5^2+1)}{(5^2-1)^2} = \frac{65}{288}$$

$\endgroup$
  • $\begingroup$ Nice answer! I didn't notice the telescoping sum allowing you to convert the denominator from $1-a^n$ to $1+a^n$ without doing any additional work. I was trying in vain to find $\sum_1^n \frac{\phi(n) q^n}{1-q^{2n}}$ to finish the answer. $\endgroup$ – Display name Feb 28 '18 at 6:58
  • $\begingroup$ Also, you didn't need to include a proof of Gauss' lemma, but since you decided to, you might as well use this simpler proof: consider the denominators of $\frac{1}{n}, \frac{2}{n}, ...., \frac{n}{n}$. When simplified, exactly $\phi(d)$ of them have denominator $d$ for any $d|n$, but this covers all of the fractions, so $\sum_{d|n} \phi(d) = n.$ $\endgroup$ – Display name Feb 28 '18 at 6:58
8
$\begingroup$

Basic facts -

  1. Using the idea behind Achille Hui's hint and noting that odd numbers can only have odd factors,

    $$\color{red}{\sum_{\textstyle{n=1\atop n\ \rm odd}}^\infty \frac{\phi(n)q^n}{1-q^{2n}}} =\sum_{\textstyle{n=1\atop n\ \rm odd}}^\infty \sum_{\textstyle{m=1\atop m\ \rm odd}}^\infty\phi(n)q^{mn} =\sum_{\textstyle{d=1\atop d\ \rm odd}}^\infty\sum_{n\mid d}\phi(n)q^d =\sum_{\textstyle{d=1\atop d\ \rm odd}}^\infty dq^d \color{red}{=\frac{q+q^3}{(1-q^2)^2}}\ .$$

  2. The extraordinary telescoping sum

    $$\color{red}{\sum_{k=0}^\infty\frac{2^k}{a^{2^k}+1}} =\sum_{k=0}^\infty\left(\frac{2^k}{a^{2^k}-1} -\frac{2^{k+1}}{a^{2^{k+1}}-1}\right) \color{red}{=\frac1{a-1}}\ .$$

  3. ${\Bbb Z}^+$ is the disjoint union of the sets $$\{\,2^km\mid m\ \hbox{is odd}\,\}$$ for $k\ge0$.
  4. If $n$ is odd and $k\ge1$ then

    $$\phi(2^kn)=2^{k-1}\phi(n)\ .$$

And now for $0<q<1$ we have $$\eqalign{ \sum_{n=1}^\infty \frac{\phi(n)}{q^{-n}+1} &=\sum_{\textstyle{n=1\atop n\ \rm odd}}^\infty\frac{\phi(n)}{q^{-n}+1} +\frac{\phi(n)}{q^{-2n}+1}+\frac{2\phi(n)}{q^{-4n}+1} +\frac{4\phi(n)}{q^{-8n}+1}+\cdots\cr &=\sum_{\textstyle{n=1\atop n\ \rm odd}}^\infty\phi(n) \left(\frac1{q^{-n}-1}-\frac1{q^{-2n}-1}\right) \qquad\qquad\hbox{using (2) twice}\cr &=\sum_{\textstyle{n=1\atop n\ \rm odd}}^\infty \frac{\phi(n)q^n}{1-q^{2n}}\cr &=\frac{q+q^3}{(1-q^2)^2}\ .\cr}$$ Finally, we get your sum by taking $q=\frac15$: $$\sum_{n=1}^\infty\frac{\phi(n)}{5^n+1}=\frac{130}{24^2}=\frac{65}{288}\ .$$

$\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.