# The most peculiar totient sum: $\sum_{n=1}^{\infty} \frac{\phi(n)}{5^n +1}$

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.

• Hint: $\sum_{n=1}^\infty \frac{\varphi(n)q^n}{1-q^n} = \frac{q}{(1-q)^2}$ for $|q| < 1$. – achille hui Feb 28 '18 at 4:34
• @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. – Display name Feb 28 '18 at 4:36
• 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}$$ – achille hui Feb 28 '18 at 4:43
• @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. – Display name Feb 28 '18 at 4:53
• 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. – achille hui Feb 28 '18 at 4:57

## 2 Answers

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}$$

• 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. – Display name Feb 28 '18 at 6:58
• 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.$ – Display name Feb 28 '18 at 6:58

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