Let $a_1, a_2, a_3, \ldots$ be a sequence of reals such that there exists $N\in\mathbb{N}$ so that $a_n=1$ for all $n\geq N$, and for all $n\geq 2$ we have \[a_{n}\leq a_{n-1}+2^{-n}a_{2n}.\]Show that $a_k>1-2^{-k}$ for all $k\in\mathbb{N}$. Proposed by usjl
Problem
Source: 2022 Taiwan TST Round 1 Independent Study 2-A
Tags: inequalities, Taiwan
Tintarn
07.07.2022 17:04
The solution consists of two steps: First, we show that w.l.o.g. we have equality everywhere. Second, we deduce the claim in that special case.
First step: W.l.o.g. equalityIndeed, suppose we have a solution with minimal $a_k$ for some fixed $k,N$ and suppose that we do not have equality for some $k<n \le N$.
Then we change $a_m$ to $a_m-\left(1-\frac{1}{2^m}\right)\varepsilon$ for all $m < n$, where $\varepsilon>0$ is sufficiently small. Indeed, if $\varepsilon>0$ is small enough, we do not change the validity of the inequality for $n$ and the inequality for all smaller indices remains valid by our choice of the shift, after a short calculation.
Second step: Finishing assuming equality everywhereWe claim that $1 \ge a_n>1-\frac{1}{2^n}$ for all $n$ which we prove by backwards induction on $n$. Indeed, for $n \ge N$ this is trivial and if it is known for $n$ and $2n$, then $a_{n-1}=a_n-\frac{a_{2n}}{2^n}$ is clearly less than $a_n$ and hence less than $1$ and on the other hand
\[a_{n-1} >1-\frac{1}{2^n}-\frac{1}{2^n}=1-\frac{1}{2^{n-1}}\]as desired.
mihaig
10.07.2022 20:13
Beautiful
USJL
11.07.2022 07:27
Proposer remark: The $2n$ in the problem statement is actually irrelevant---it can be replaced by any integer that is strictly larger than $n$. The inequality is taken (as a special case) from Terrance Tao's lecture notes on the Kakeya conjecture---see the document in https://artofproblemsolving.com/community/c6h2784600p24469107 for more
CANBANKAN
11.07.2022 19:17
The idea is that the $a_i$'s linearly affect each other, so we can use greedy algorithm. Let $b_j$ satisfy the recurrence $b_n=1\forall n\ge N$ and $b_{n-1}=b_n-2^{-n}b_{2n}$ for all $n\le N$ Let $x_n=a_{n-1}+2^{-n}a_{2n}-a_n\ge 0$ for all $2\le n\le N$. The key insight is that $a_k\ge b_k$. In fact, I claim there exists positive constants $c_{i,j}$ where $1\le i\le j\le N$ such that $$a_i=b_i+\sum\limits_{j\ge i} c_{i,j}x_j$$ To see this; we induct on $i$ from large to small; note $$a_{i-1}=a_i-2^{-i}a_{2i} + x_{i-1} = (b_i-2^{-i}b_{2i}) \sum\limits_{j\ge i+1} (c_{i,j}-2^{-i}c_{2i,j}) x_j + (1)x_{i-1}$$ ($c_{j,k}=0$ if $k<j$) Therefore, $c$ obeys the recursion $c_{i,i}=1$ and $c_{i-1,j}=c_{i,j}-2^{-i}c_{2i,j}$. Since we can show $c\le 1$, it also follows that $c\ge 0$. It remains to show $b_k>1-2^{-k}$, which can be easily proven via induction and the fact that $b_k<1$.
Iveela
21.04.2024 16:35
Suppose the contrary. Then our condition implies that there exists a $k \in \mathbb{N}$ such that $a_{k-1} \leq 1 - \frac{1}{2^{k-1}}$ and $a_k > 1 - \frac{1}{2^k}$. Observe that \[1 -\frac{1}{2^k} < a_k \leq a_{k-1} + \frac{a_{2k}}{2^k} \leq 1 - \frac{1}{2^{k-1}}+\frac{a_{2k}}{2^k} \implies 1 < a_{2k}\]Since our sequence is eventually constant, we may consider $a_n = \max \{a_i \mid i \geq k-1\}$. Note that $a_n \geq a_{2k}>1$. We will show using induction that for every positive integer $m \leq n-k+1$ we have \[1-\frac{1}{n-m} < a_n(1-\sum\limits_{i=0}^{m-1}\frac{1}{2^{n-i}}) \leq a_{n-m}\]Observe that if our claim is indeed true, we will have $a_{k-1}>1-\frac{1}{2^{k-1}}$, a contradiction. For the base case $m=1$, we simply have $a_n \leq a_{n-1}+\frac{a_{2n}}{2^n} \leq a_{n-1} + \frac{a_n}{2^n}$ which implies $a_n(1-\frac{1}{2^n}) \leq a_{n-1}$. Now suppose that our claim holds for $m-1$. Since $2(n-m+1) \geq k-1$, our condition implies that \[a_n(1-\sum\limits_{i=0}^{m-2} \frac{1}{2^{n-i}}) \leq a_{n-m+1} \leq a_{n-m}+\frac{a_{2(n-m+1)}}{2^{n-m+1}} \leq a_{n-m} + \frac{a_n}{2^{n-m+1}} \implies a_n(1-\sum\limits_{i=0}^{m-1} \frac{1}{2^{n-i}}) \leq a_{n-m}\]which is what we wanted to prove. $\blacksquare$