Home » Uncategorized » \varphi summation

\varphi summation

Let \varphi denote the Euler’s function. Prove that

    \[\sum_{k=1}^{\infty} \varphi(k) \left \lfloor \frac{n}{k} \right \rfloor = \frac{n \left ( n+1 \right )}{2}\]

Solution

The key idea is to rewrite the floor as a sum involving divisors. Hence,

    \begin{align*} \sum_{k=1}^{\infty} \varphi(k) \left \lfloor \frac{n}{k} \right \rfloor &= \sum_{k=1}^{\infty} \varphi(k) \sum_{\substack{m \leq n \\ k \mid n}} 1 \\ &= \sum_{k=1}^{\infty} \sum_{\substack{m \leq n \\ k \mid n}} \varphi(k) \\ &= \sum_{m=1}^{n} \sum_{k \mid m} \varphi(k) \\ &= \sum_{m=1}^{n} m \\ &= \frac{n \left ( n+1 \right )}{2} \end{align*}

Read more

Leave a comment

Donate to Tolaso Network