Maths Olympiad Prep

Library / /13 of 15

Number theory Difficulty 6.0 National Olympiad Prove it Philippines

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

Solution

Solution:
We compute
∑n=1∞φ(n)4n7n−4n=∑n=1∞φ(n)(47)n1−(47)n=∑n=1∞φ(n)∑k=1∞(47)nk \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 ∑d∣nφ(d)=n\sum_{d \mid n} \varphi(d) = n where the sum takes all over positive divisors of nn, we arrive at
∑n=1∞φ(n)4n7n−4n=∑n=1∞φ(n)∑k=1∞(47)nk=∑m=1∞(47)m∑d∣mφ(d)=∑m=1∞m(47)m=47(1−47)2=289 \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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