Show it is true when is a prime power. Then use induction. Prove it is true for n=1, then assume it is true for all numbers up to n. If n+1 is a prime power, you already proved it is true. Otherwise, use the fact that f(n+1) = f(a)f(b) where b is a prime power, a and b are coprime, and ab=n+1. Both a and b will therefore be less than n, so you can apply the induction hypothesis.