This is an exercise from Problems from the Book by Andreescu and Dospinescu. When it was posted on AoPS a year ago I spent several hours trying to solve it, but to no avail, so I am hoping someone here can enlighten me.

Problem: Prove that the function $f : [0, 1) \to \mathbb{R}$ defined by

$\displaystyle f(x) = \log_2 (1 - x) + x + x^2 + x^4 + x^8 + ...$

is bounded.

A preliminary observation is that $f$ satisfies $f(x^2) = f(x) + \log_2 (1 + x) - x$. I played around with using this functional equation for awhile, but couldn't quite make it work.

  • 1
    $\begingroup$ if you differentiate your functional equation you get that limx→1f′(X)lim_{x\to 1} f'(X) exists and is finite. doesn't that do it for you? $\endgroup$ Aug 3 '10 at 0:46
  • 1
    $\begingroup$ Hmm. Maybe. If you wrote that up together with a proof that f' actually exists, I'll accept it. That seems too easy, somehow. $\endgroup$ Aug 3 '10 at 1:11
  • $\begingroup$ A lot of solutions people claim are "from the book" are short and sweet :) $\endgroup$ Aug 3 '10 at 1:23
  • 1
    $\begingroup$ Plotting the function in Mathematica seems to indicate otherwise... $\endgroup$ Aug 3 '10 at 1:56
  • 1
    $\begingroup$ @Danny: it is only being claimed that the problems, not their solutions, are from the Book! The authors, by their own admission, don't know how to solve some of the exercises... $\endgroup$ Aug 3 '10 at 2:02

OK, a second trick is needed (but it actually finishes the problem). It is nice and simple enough that it's probably what the authors intended by a "Book" solution.

Let $f(x) = x \log(2) - \log(1+x)$. We want to show that $S(x) = f(x) + f(x^2) + f(x^4) + \dots$ is bounded. Because $f(0)=f(1)=0$ and $f$ is differentiable, we can find a constant $A$ such that $|f(x)| \leq Ax(1-x) = Ax - Ax^2$. The sum of this bound over the powers $x^{2^k}$ is telescopic.

Notice that the role of $\log(2)$ was to ensure that $f(1)=0$.

  • 5
    $\begingroup$ Very nice! (and extra characters to satisfy the silly 15 character limit) $\endgroup$ Aug 3 '10 at 19:21
  • $\begingroup$ "Because f(0) = f(1) = 0 and f is differentiable, we can find a constant A..." ??? could you clarify? I'm missing something, is that the extreme value theorem? en.wikipedia.org/wiki/Extreme_value_theorem $\endgroup$
    – Jason S
    Aug 3 '10 at 22:25
  • 3
    $\begingroup$ g(x) = f(x)/(x(1-x)) is defined on (0,1) and extends to a continous function on [0,1]. The extension exists because the limits of g(x) needed at the endpoints are f'(0) and f'(1). So differentiability of f(x) at 0 and 1 implies continuity of g(x), and for A just take any upper bound on the values of |g(x)| in [0,1]. $\endgroup$
    – T..
    Aug 3 '10 at 22:39

Starting from (the natural logarithm of) $(1-x)^{-1} = (1+x)(1+x^2)(1+x^4) \dots$, it becomes clearer where the $\log(2)$ factor comes from.

One has to show that $\Sigma (x^{2^k} - C\log(1 + x^{2^k}))$ is bounded sum of positive terms. The sum of the first $n$ terms approaches $n - Cn\log(2)$ as $x \to 1-$, so we need $C = 1/\log(2)$ if there is to be boundedness.

  • 1
    $\begingroup$ Nice observation. Can you finish the argument from here? $\endgroup$ Aug 3 '10 at 3:07
  • $\begingroup$ Yes and no. I posted a completion of the proof (see other answer) but it requires an additional, independent observation. $\endgroup$
    – T..
    Aug 3 '10 at 19:04

If anyone's interested, here's another approach.

First, observe that $$ \log{2} = \int_{2^r}^{2^{r+1}} \frac{1}{x}\;dx \le \sum_{k=2^r}^{2^{r+1}-1}\frac{1}{k} \le \int_{2^r-1}^{2^{r+1}-1} \frac{1}{x}\;dx = \log{2} + \log\left(1+\frac{1}{2^{r+1}-2}\right) $$ for $r\ge1$, so using $\log(1+x) \le x$ (for $x>-1$) and $2^{r+1} - 2 \ge 2^r$, we get $$ \log{2} \le \sum_{k=2^r}^{2^{r+1}-1} \frac{1}{k} \le \log{2} + \frac{1}{2^r} $$ for all $r\ge0$ (check directly for $r=0$).

Thus for $x\in[0,1)$, we have $$\begin{align*} \lvert f(x)\log{2}\rvert = \lvert\sum_{r\ge0} x^{2^r}\log{2} - \sum_{n\ge1} \frac{x^n}{n}\rvert &= \lvert\sum_{r\ge0} x^{2^r}(\log{2} - \sum_{k=2^r}^{2^{r+1}-1}\frac{1}{k}) + \sum_{r\ge0}\sum_{k=2^r}^{2^{r+1}-1}\frac{x^{2^r} - x^k}{k} \rvert \\ &\le \sum_{r\ge0}\frac{x^{2^r}}{2^r} + \sum_{r\ge0}\sum_{k=2^r}^{2^{r+1}-1}\frac{x^{2^r} - x^k}{k} \\ &< 2 + \sum_{r\ge0}x^{2^r}(1-x)\sum_{k=2^r}^{2^{r+1}-1}\frac{1+x+\cdots+x^{k-2^r-1}}{k} \\ &\le 2 + (1-x)\sum_{r\ge0}x^{2^r}\sum_{k=2^r}^{2^{r+1}-1}\frac{k-2^r}{k} \\ &\le 2 + (1-x)\sum_{r\ge0}x^{2^r}(2^r\cdot 1) \\ &\le 2 + (1-x)(x + 2\sum_{r\ge1}\sum_{k=2^{r-1}+1}^{2^r}x^k) \\ &= 2 + x(1-x) + 2(1-x)\sum_{k\ge2} x^k \\ &= 2 + x + x^2, \end{align*}$$ so we're done.


Solution using minimal calculus: Let $y=1-x$ and $z=\lfloor{\log_2(\frac{1}{1-x})}\rfloor$.

Lemma $1$:

$x^{2^{n}} \geq (1-2^{n-1}y),\; \forall n \in \mathbb{N^+}$.


We proceed by induction. For the base case $n=1$, we have $1 \geq 1-y$. Suppose this is true for $n$. Then, assuming $1-2^{n}y \geq 0$, $x^{2^{n+1}}=\left(x^{2^{n}}\right)^{2}$ $\geq \left(1-2^{n}y\right)^{2} = 1-2^{n+1}y+2^{2n}y^{2} \geq 1-2^{n+1}y$. If $1-2^{n}y < 0$, then this is obviously true.

We have $$\log_2(1-x)+\sum_{i=1}^\infty x^{2^{i}} \\= \sum_{i=1}^\infty x^{2^{i}}-\log_2\left(\dfrac{1}{1-x}\right) \\\geq \sum_{i=0}^z (1-2^{i}y)-\log_2(1-x)\\= \left\lfloor{\log_2\left(\frac{1}{1-x}\right)}\right\rfloor+1-\log_2\left(\frac{1}{1-x}\right)-\left(2^{z+1}-1\right)y \geq -2.$$

It is also well known that $x^{2^{z+1}} \leq \frac{1}{e}$, so $$\sum_{i=1}^\infty x^{2^{i}}+\log_2(1-x) \\= \sum_{i=1}^\infty x^{2^{i}}-\log_2\left(\dfrac{1}{1-x}\right) \\\leq \sum_{i=1}^z x^{2^{i}}+\sum_{i=1}^\infty x^{i2^{z+1}}-\log_2\left(\dfrac{1}{1-x}\right) \\\leq \left\lfloor {\log_2\left(\dfrac{1}{1-x}\right)}\right\rfloor-\log_2(\dfrac{1}{1-x})+\dfrac{1}{e-1} \\\leq \dfrac{1}{e-1}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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