$\sum \frac{1}{f(k)}$ converges iff $\sum \frac{f^{-1}(k)}{k^2}$ converges Let $f$ be a strictly increasing positive continuous function defined on $[1,\infty)$ with limit $\infty$ as $x$ goes towards $\infty$. Then $\sum_{k=0}^{\infty} \frac{1}{f(k)}$ converges if and only if $\sum_{k=0}^{\infty} \frac{f^{-1}(k)}{k^2}$ converges, where $f^{-1}$ denotes the inverse of $f$. 
I saw this claim as an exercise in a analysis textbook, linked from this site. Can not remember which one unfortunately. It was listed as a challenging exercise and has proven too challenging for me.  
My initial idea was to try to use the integral test. $\sum \frac{1}{f(k)}$ converges exactly when $\int \frac{1}{f(x)}$ converges. I thought I might do some smart change of variable to find that $\int \frac{f^{-1}(x)}{x^2}$ converges. I could not come up with one however and I also realized that I do not know that the sum $\sum \frac{f^{-1}(k)}{k^2}$ satisfies the conditions for using the integral test. Unfortunately I ran out of ideas at that point. 
 A: Define $A(n)$ to be $\{k: 2^n \leq f(k) < 2^{n+1}\}$, and $|A(n)|$ its cardinality. Let $S_n$ be the sum of the terms of the first sequence over $k$ in $A_n$. Then we have
$${1 \over 2^{n+1}}|A(n)| < S_n \leq {1 \over 2^n}|A(n)|$$
Thus the first sum $\sum_n S_n$ is within a factor of $2$ of ${\displaystyle \sum_n {|A(n)| \over 2^n}}$.
Next, let $T_n$ be the sum of the terms of the second sequence over $2^n \leq k < 2^{n+1}$. In the sum $T_n$, since $f^{-1}$ is increasing, $f^{-1}(k)$ is less than $f^{-1}(2^{n+1}) = \sum_{m \leq n+1}|A(m)|$, and at least $f^{-1}(2^n) = \sum_{m \leq n}|A(m)|$. There are $2^n$ terms in the sum defining $T_n$, so we have
$$2^{-2(n+1)}2^n\sum_{m \leq n}|A(m)| \leq T_n < 2^{-2n}2^n\sum_{m \leq n+1}|A(m)|$$
Summing the above in $n$, we have that $\sum_n T_n$ is within a constant factor of 
$$\sum_n 2^{-n} \sum_{m \leq n} |A(m)|$$
Switching the order of summation, this becomes
$$\sum_m |A(m)| \sum_{n \geq m} 2^{-n}$$
$$= 2\sum_m{|A(m)| \over 2^m}$$
This is within a constant factor of $\sum_n {S_n}$ computed above, so one series converges iff the other one does.
A: Use one further change of variable. Define $g(x) = 1/f(x)$. Then $g(x)$ is a strictly decreasing continuous function mapping $[1,\infty)$ to $(0,c]$. Without loss of generality we can take $c = 1$. Observe that $f^{-1}(x) = g^{-1}(1/x)$. 
So it is enough to show that $\sum g(k)$ converges iff $\sum \frac{1}{k^2}g^{-1}(\frac{1}{k})$. (Note that here if you use the integral test you do not need to use $g$ is differentiable). 
Observe that the partial sums and partial integrals have the following relation
$$ \sum_{k = n+1}^{N+1} g(k) \leq \int_n^N g(x) dx \leq \sum_{k=n}^{N} g(k) $$
Using monotonicity of $g$. Hence $\sum g(k)$ converges IFF the integral converges. 
Now look at the following (the leading 1 comes from the assumption that $g(1) = 1$:
$$ 1 + \int_1^\infty g(x) dx = \int_0^1 g^{-1}(y) dy = \int_1^{\infty} \frac{g^{-1}(\frac1y)}{y^2} dy $$
which is the integral version of what we want to prove. But in any case, consider the partial Riemann sums
$$ \sum_{k = n}^N \left(\frac{1}{k} - \frac{1}{k+1}\right)g^{-1}(\frac{1}{k}) \leq \int_{N^{-1}}^{n^{-1}} g^{-1}(y) dy \leq \sum_{k = n}^N \left(\frac{1}{k} - \frac{1}{k+1}\right)g^{-1}(\frac{1}{k+1}) $$
using now the monotonicity of $g^{-1}(y)$. Now notice that $\frac{1}k - \frac{1}{k+1} \sim \frac{1}{k^2}$ (in the sense that one can be controlled by the other by constant factors), you have that the partial sum
$$ \sum_{k = n}^N \frac{g^{-1}(\frac{1}{k})}{k^2} $$
is comparable to 
$$ \int_{N^{-1}}^{n^{-1}} g^{-1}(y) dy $$
and hence their convergences imply each other. 
Chain everything together you have the desired result. 
A: As the OP noted, by the integral test the sum converges iff $\int_0^\infty dx\,\frac{1}{f(x)}$ converges. Integrating by parts, we obtain
$$\int_0^\infty dx\,\frac{1}{f(x)} = - \int_0^\infty dx\, \frac{x f'(x)}{f(x)^2}.$$
Changing the integration variable from $x$ to $y=f(x)$ (which is admissible as $f(x)$ is monotonously increasing) yields
$$\int_0^\infty dx\,\frac{1}{f(x)}= - \int_{f(0)}^\infty dy\, \frac{f^{-1}(y)}{y^2}.$$ Using the integral test again, we have that the original series converges iff $$\sum \frac{f^{-1}(k)}{k^2}$$ converges.
Edit: (trying to incorporate some comments)
1) the OP did not specify that $f$ is differentiable. One can use a Spline interpolation to make $f \in C^1$. (thaks to user7530)
2) there was a question about the fate of the boundary term $x f(x)$: one should prove the argument in two steps. First assume $\sum f(k)^{-1}$ converges, then the boundary term is zero as $f(k)$ falls off faster than $k^{-1}$ and you can prove that $\sum \frac{f^{-1}(k)}{k^2}$ converges. Then the other way round, assume $\sum \frac{f^{-1}(k)}{k^2}$ converges. The boundary term then reads $f^{-1}(y) y$ which you can prove to be finite by the same method and thereby showing that $\sum f(k)^{-1}$ converges.
