11
$\begingroup$

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.

  • 0
    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.2011-03-03
  • 0
    @Michael Lugo: the second sum should be $\sum k^{1/\alpha-2}$2011-03-03
  • 0
    @Fabian: you're right. thanks.2011-03-04

3 Answers 3

2

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.

13

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.

  • 2
    Why should the integrals/derivatives even exist?2011-03-04
  • 1
    Can we just define $f(x)$ for non-integer $x$ by linear interpolation?2011-03-04
  • 1
    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.2011-03-04
  • 0
    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 ...2011-03-04
  • 1
    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)...2011-03-04
  • 0
    How do you know that $f^{-1}(x)/x^2$ fulfills the conditions for using the integral test so that we can conclude convergence of the sum from the existence of the integral? (And regarding differentiability, there was no such requirement in the original exercise but I did forget to specify that $f$ is continuous.2011-03-04
  • 0
    I don't know. So the argument is not yet complete...2011-03-04
4

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.