$\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.

-
Just a note: if $f(k) = k^\alpha$ for some $\alpha > 0$, then this reduces to the claim that $\sum k^{-\alpha}$ converges iff $\sum k^{\alpha-2}$ converges, which is true. This is of course not a proof, but it's a good sanity check. –  Michael Lugo Mar 3 '11 at 22:42
@Michael Lugo: the second sum should be $\sum k^{1/\alpha-2}$ –  Fabian Mar 3 '11 at 22:47
@Fabian: you're right. thanks. –  Michael Lugo Mar 4 '11 at 2:48

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.

-

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.

-
Why should the integrals/derivatives even exist? –  Aryabhata Mar 4 '11 at 2:03
Can we just define $f(x)$ for non-integer $x$ by linear interpolation? –  Michael Lugo Mar 4 '11 at 2:48
Not really, because f' won't exist at the transition points. But along those lines, you can take f restricted to $\mathbb{Z}$ and extend it to a monotonic $C^1$ function using any number of higher-order spline interpolation schemes. The bigger problem is what to do if the integral of x/f(x) diverges. –  user7530 Mar 4 '11 at 5:22
As far as I understand: as long as $f(x)= O(x)^{\alpha}$ with $\alpha>1$ (such that the sum converges) then $x/f(x) =0$ on the boundaries. If it diverges then ... –  Fabian Mar 4 '11 at 6:41
In principle have all the operations involved (partial integration, change of variables) and analog in terms of sum without resorting to integrals. I guess along those line one could give a proof without resorting to derivatives (but only to finite differences)... –  Fabian Mar 4 '11 at 6:44

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.

-