Let $0<k<\frac{1}{2}$ be a real number and let $a_0, b_0$ be arbitrary real numbers in $(0,1)$. The sequences $(a_n)_{n\ge 0}$ and $(b_n)_{n\ge 0}$ are then defined recursively by $$a_{n+1} = \dfrac{a_n+1}{2} \text{ and } b_{n+1} = b_n^k$$ for $n\ge 0$. Prove that $a_n<b_n$ for all sufficiently large $n$. Proposed by Michael Ma
Problem
Source: 2017 ELMO Shortlist A1
Tags: algebra
03.07.2017 05:20
Define $a=1-a_0$ and $b=1-b_0$. By induction, $a_n = 1-\frac{a}{2^n}$ and $b_n=(b_0)^{k^n} = (1-b)^{k^n}$ for all $n\geq 0$. By Bernoulli's inequality, $(1-b)^{1+k^n}\geq 1-(1+k^n)b$ (the $1$ is added to the exponent to make sure that it's $>1$) Therefore, $(1-b)^{k^n} \geq \frac{1-(1+k^n)b}{1-b} = 1-\frac{k^nb}{1-b}$. Now, for sufficiently large $n$, $\left(\frac{1}{2k}\right)^n > \frac{b}{a(1-b)}$, which implies $b_n \geq 1-\frac{k^nb}{1-b} > 1-\frac{a}{2^n} = a_n.$
03.07.2017 05:20
Here is my solution
18.11.2020 10:06
Solved with willwin4sure. Let $c_n:=1-a_n$, so that $c_{n+1}=\tfrac12 c_n$. Hence $c_n=\tfrac{1}{2^n}c_0$, and also $b_n=b_0^{k^n}$. We want to show $b_n+c_n>1$ for all large enough $n$. For a fixed $n$, note \begin{align*} b_n+c_n > 1 &\iff \tfrac{c_0}{2^n} + b_0^{k^n} > 1 \\ &\iff b_0^{k^n} > 1-\tfrac{c_0}{2^n} \\ &\iff k^n\log(b_0) > \log(1-\tfrac{c_0}{2^n}) \\ &\impliedby k^n\log(b_0) > -\tfrac{c_0}{2^n} \\ &\iff (2k)^n < -\tfrac{c_0}{\log(b_0)}. \end{align*}In the fourth step, we used the estimate $\log(1-x) < -x$ for positive $x$, and in the final step, we switched the inequality sign since $\log(b_0)<0$ since $b_0<1$. However, the final condition is true for large enough $n$ since $0<2k<1$, so we are done.
11.06.2021 18:10
what does it mean by all sufficiently large.
12.06.2021 15:21
Let $a=1-a_0$ and $b=1-b_0$. It's not hard to see that $a_n=1-\tfrac{a}{2^n}$ and $b_n=(1-b)^{k^n}$ for all $n \geq 0$. By Bernoulli, we have $$b_n=\frac{(1-b)^{k^n+1}}{1-b}\geq \frac{1-(k^n+1)b}{1-b}=1-\frac{k^nb}{1-b}.$$It is clear that we are done if we can show that $\tfrac{a}{2^n}>\tfrac{k^nb}{1-b}$ for all sufficiently large $n$. This rearranges as $$\left(\frac{1}{2k}\right)^n>\frac{b}{a(1-b)},$$which is true for all sufficiently large $n$ due to asymptotics and the fact that $\tfrac{1}{2k}>1$. $\blacksquare$
30.03.2022 18:27
Let $x_n=1-a_n$ and $y_n=b_n$ and $x_0=x$ and $1-y_0=y$. Then $x_{n+1}=\frac{x_n}2$, giving the general forms $x_n=\frac x{2^n}$ and $y_n=(1-y)^{k^n}$. Then, for sufficiently large $n$: $$y_n=(1-y)^{k^n}=\frac{(1-y)^{1+k^n}}{1-y}\ge\frac{1-(1+k^n)y}{1-y}=1+\frac{k^ny}{y-1}.$$by Bernoulli's inequality. Then: $$x_n+y_n\ge\frac x{2^n}+\frac{k^ny}{y-1}+1,$$so it suffices to show that $x_n+y_n>1$, or $\frac x{2^n}+\frac{k^ny}{y-1}>0$. This is equivalent to $(2k)^n<\frac xy-x$, which is true for large enough $n$ as $\frac xy-x>x-x=0$.
04.08.2024 11:16
Solving the recurrences we find that $a_n=1-(1-a_0)/2^n$ and $b_n=b_0^{k^n}$. Note that $$b_n=\frac{(1-(1-b_0))^{k^n+1}}{b_0}\geq \frac{1-(1-b_0)(k^n+1)}{b_0}=1-\frac{1-b_0}{b_0}k^n$$by Bernoulli's inequality. Since $0<k<1/2$, it follows that $\left (\frac 1{2k}\right)^n \to \infty$ as $n\to \infty$. Hence there is a $N$ such that $$\left (\frac 1{2k}\right)^n >\frac{1-b_0}{b_0(1-a_0)} \Rightarrow 1-\frac{1-b_0}{b_0}k^n > 1-(1-a_0)/2^n$$for all $n\geq N$. It follows that $b_n>a_n$ for all $n\geq N$ and we're done.
13.11.2024 19:46
Let $a = 1 - a_0$ and $b = 1 - b_0$. Observe that $$ a_n = a_0 + (1 - a_0) \left(1 - \frac{1}{2^n}\right) = 1 - a + a \left(1 - \frac{1}{2^n}\right) = 1 - \frac{a}{2^n} $$On the other hand, by Bernoulli's inequality $$ b_n = \frac{(1 - b)^{K^n + 1}}{1 - b} \geq \frac{1 - b(K^n + 1)}{1 - b} = 1 - \frac{b K^n}{1 - b} $$Thus, it suffices to show that $ \frac{a}{2^n} > \frac{b K^n}{1 - b} $ for $n$ sufficiently large. For this, observe that $$ \frac{a}{2^n} > \frac{b K^n}{1 - b} \Longleftrightarrow \frac{a}{(2K)^n} > \frac{b}{1 - b} $$Since $ K < \frac{1}{2} $, we have $ \lim_{n \to \infty} (2K)^n = 0 $, so the inequality holds for $ n $ sufficiently large, and we are done.
13.01.2025 07:15
Let $a_0 = 1-\alpha$ and $b_0 = e^{-\beta}$; then, $1-a_n = \alpha/2^n$ and $b_n = e^{-\beta k^n}$. Hence \[ b_n + (1-a_n) = e^{-\beta k^n} + \alpha/2^n > 1 - \beta k^n + \alpha/2^n \overset{(\ast)}> 1, \]where $(\ast)$ is true for sufficiently large $n$ because it is equivalent to $\tfrac{\alpha}{\beta} > (2k)^n$, and $(2k)^n \to 0$ since $2k < 1$. $\blacksquare$