Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.