32
$\begingroup$

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.

$\endgroup$
6
  • 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, 2010 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, 2010 at 1:11
  • $\begingroup$ A lot of solutions people claim are "from the book" are short and sweet :) $\endgroup$ Aug 3, 2010 at 1:23
  • 1
    $\begingroup$ Plotting the function in Mathematica seems to indicate otherwise... $\endgroup$ Aug 3, 2010 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, 2010 at 2:02

4 Answers 4

32
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ Very nice! (and extra characters to satisfy the silly 15 character limit) $\endgroup$ Aug 3, 2010 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, 2010 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, 2010 at 22:39
14
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Nice observation. Can you finish the argument from here? $\endgroup$ Aug 3, 2010 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, 2010 at 19:04
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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^+}$.

Proof:

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

$\endgroup$

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.