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

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.

share|cite|improve this question
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? – Eric O. Korman Aug 3 '10 at 0:46
Hmm. Maybe. If you wrote that up together with a proof that f' actually exists, I'll accept it. That seems too easy, somehow. – Qiaochu Yuan Aug 3 '10 at 1:11
A lot of solutions people claim are "from the book" are short and sweet :) – BlueRaja - Danny Pflughoeft Aug 3 '10 at 1:23
Plotting the function in Mathematica seems to indicate otherwise... – Mariano Suárez-Alvarez Aug 3 '10 at 1:56
@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... – Qiaochu Yuan Aug 3 '10 at 2:02
up vote 27 down vote accepted

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

share|cite|improve this answer
Very nice! (and extra characters to satisfy the silly 15 character limit) – Mariano Suárez-Alvarez Aug 3 '10 at 19:21
"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? – Jason S Aug 3 '10 at 22:25
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]. – 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.

share|cite|improve this answer
Nice observation. Can you finish the argument from here? – Qiaochu Yuan Aug 3 '10 at 3:07
Yes and no. I posted a completion of the proof (see other answer) but it requires an additional, independent observation. – 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.

share|cite|improve this answer

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}$$

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.