Library / Philippine Mathematical Olympiad, National Orals /13 of 15

Philippine Mathematical Olympiad, National Orals

Number theory Difficulty 6.0 National Olympiad Prove it Philippines

Problem:
For each positive integer $n$ , let $\varphi(n)$ be the number of positive integers from $1$ to $n$ that are relatively prime to $n$ . Evaluate
$\sum_{n=1}^{\infty} \frac{\varphi(n) 4^{n}}{7^{n}-4^{n}}$

Solution

Solution:
We compute
$\sum_{n=1}^{\infty} \frac{\varphi(n) 4^{n}}{7^{n}-4^{n}} = \sum_{n=1}^{\infty} \varphi(n) \frac{\left(\frac{4}{7}\right)^{n}}{1-\left(\frac{4}{7}\right)^{n}} = \sum_{n=1}^{\infty} \varphi(n) \sum_{k=1}^{\infty}\left(\frac{4}{7}\right)^{n k}$
Interchanging the order of summation and using the fact that $\sum_{d \mid n} \varphi(d) = n$ where the sum takes all over positive divisors of $n$ , we arrive at
$\begin{aligned} \sum_{n=1}^{\infty} \frac{\varphi(n) 4^{n}}{7^{n}-4^{n}} & = \sum_{n=1}^{\infty} \varphi(n) \sum_{k=1}^{\infty}\left(\frac{4}{7}\right)^{n k} = \sum_{m=1}^{\infty}\left(\frac{4}{7}\right)^{m} \sum_{d \mid m} \varphi(d) \\ & = \sum_{m=1}^{\infty} m\left(\frac{4}{7}\right)^{m} = \frac{\frac{4}{7}}{\left(1-\frac{4}{7}\right)^{2}} = \frac{28}{9} \end{aligned}$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.