When does the series $\sum_{n=1}^\infty \frac 1{nf(n)}$ converges? Let $f : \Bbb{N}\longrightarrow \Bbb{N}$ be a function. 
a. Suppose $M$ is fixed and for any $n$, $|f^{-1}(\{n\})| < M$. Show that $\sum_{n=1}^\infty \frac 1{nf(n)}$ is convergent. 
b. Suppose that for any $n$, $f^{-1}(\{n\})$ is finite. Does it mean that the series $\sum_{n=1}^\infty \frac 1{nf(n)}$ must be convergent !?
 A: First, the answer to (b) is no. Put $f(k) = n$ for $k = 2^{n-1},\dots,2^n - 1$. Then
\begin{align*}
\sum_{n=1}^\infty {1\over nf(n)} & = \sum_{m=1}^\infty {1\over m}\sum_{n\in f^{-1}(m)}{1\over n} \\
& = \sum_{m=1}^\infty {1\over m}\sum_{n=2^{m-1}}^{2^m-1}{1\over m}\\
& \geq \sum_{m=1}^\infty {1\over m} \left({2^m-1-2^{m-1}\over 2^m}\right),
\end{align*}
and the last sum diverges by comparison to the harmonic series.
For (a), start with summation by parts. Put $s_n = \sum_{k = 1}^n 1/f(k)$ and $s_0 = 0$ and write
\begin{align*}
\sum_{n=1}^N{1\over nf(n)} & = \sum_{n=1}^N{1\over n} (s_n-s_{n-1}) \\
& = {s_N\over N} + \sum_{n =1}^{N-1}s_n\left({1\over n}-{1\over n+1}\right) \\
& = {s_N\over N} + \sum_{n=1}^{N-1}{s_n\over n(n+1)}
\end{align*}
Now let's bound $s_n$; I claim that $s_n = O(\log{n})$—this is plainly sufficient to ensure convergence. To prove this, write
\begin{align*}
s_n & = \sum_{k = 1}^n{1\over f(k)} = \sum_{m = 1}^\infty {|f^{-1}(m)\cap \{k\in\mathbb N:k\leq n\}|\over m} \leq M \sum_{m=1}^n {1\over m}.
\end{align*}
The reason for the last inequality is simply this: There are at most $n$ positive integers $m$ for which the quantity $|f^{-1}(m)\cap \{k\in\mathbb N:k\leq n\}|$ is nonzero—it is in all cases bounded by $M$—and the sum above will be maximized if the quantity is nonzero for the smallest integers $m$ available, namely, $1,\dots,n$. Thus the inequality holds. Finally, the last sum is $O(\log{n})$, so the bound is proved and we are done with (a).
