Sum of Eulers phi function

Question

Given that $p$ is a prime number, how would one calculate the sum: $$\sum_{k=0}^{n} {\phi (p^k)} $$ I know from Euler's phi function that if $p$ is a prime number then: $${\phi (p^k)} = {p^{k-1}}(p-1) = p^k-p^{k-1} $$ but here I'm stuck. any clues or help would be really appreciated, thanks!

Answer 1

As you noted, what we're interested in is really $$\sum_{k=0}^n (p^k - p^{k-1}). $$

Writing it out, we can see that it is a telescoping sum: $$(p^n - p^{n-1}) + (p^{n-1} - p^{n-2}) + \dots + (p - 1) + 1.$$

Answer 2

$$\sum_{k=0}^n \phi (p^k) = \sum_{k=0}^np^{k-1}(p-1) = 1+\sum_{k=1}^np^{k-1}(p-1) $$ $$\ = 1+(p-1)+(p^2-p)+...... (p^k-p^{k-1})+ ...... (p^n-p^{n-1})$$ which is a telescopic sum Therefore, it simplifies to $$\ p^n $$ And we are done :-)