Let $ \left(a_{n}\right)$ be the sequence of reals defined by $ a_{1}=\frac{1}{4}$ and the recurrence $ a_{n}= \frac{1}{4}(1+a_{n-1})^{2}, n\geq 2$. Find the minimum real $ \lambda$ such that for any non-negative reals $ x_{1},x_{2},\dots,x_{2002}$, it holds \[ \sum_{k=1}^{2002}A_{k}\leq \lambda a_{2002}, \] where $ A_{k}= \frac{x_{k}-k}{(x_{k}+\cdots+x_{2002}+\frac{k(k-1)}{2}+1)^{2}}, k\geq 1$.
Problem
Source: China Team Selection Test 2002, Day 1, Problem 2
Tags: algebra unsolved, algebra
17.11.2006 07:51
Does somebody has solution to this Chinese problem?
20.08.2015 23:28
We start by cleaning some scariness from the problem. Let $t=2002$. For $k=1,2,\dots,t$, set $$y_k=x_k+x_{k+1}+\dots+x_t+\frac{k(k-1)}2+1,$$ moreover define $L:=y_{t+1}:=\frac{(t+1)t}2+1$. Then since $\frac{k(k-1)}2-\frac{k(k+1)}2=-k$, we have $y_k-y_{k+1}=x_k-k$ for each $1\le k\le t$. Hence, the sum we want to maximize is $$S:=\sum_{k=1}^{2002}A_k=\sum_{k=1}^{2002} \frac{y_k-y_{k+1}}{y_k^2}.$$ We will solve the problem when the $y_k$ are arbitrary positive reals, and leave it for later to settle the nitpickiness of whether the $x_k$'s yielding the maximum are positive or not. Lemma 1. The inequality $\frac{ax-b}{x^2}\le \frac{a^2}{4}\cdot \frac1{b}$ is true $\forall x\in\mathbb{R}\setminus\{0\}$ and equality holds exactly when $x=\frac{2b}{a}$, where $a,b>0$. Proof. Multiplying by $4bx^2>0$, we need $4abx-4b^2\le a^2x^2$, i.e. $(ax-2b)^2\ge 0$. $\blacksquare$ (We derived this inequality by setting $X=\frac 1x$, as it becomes a quadratic maximization problem.) Lemma 2. Define the sequence $b_1=0$, and $b_n=\frac14(1+b_{n-1})^2$, $n\ge 2$. Then we have $$\frac{b_k}{y_k}+\frac{y_k-y_{k+1}}{y_k^2}\le \frac{b_{k+1}}{y_{k+1}}$$ for all $1\le k\le n$. Proof. Employing Lemma 1, we find that $$\frac{b_k}{y_k}+\frac{y_k-y_{k+1}}{y_k^2}=\frac{(b_k+1)y_k-y_{k+1}}{y_k^2}\le $$ $$\le \frac{(b_k+1)^2}{4}\cdot \frac1{y_{k+1}}=\frac{b_{k+1}}{y_{k+1}}.\quad \blacksquare$$ Now, adding these inequalities for $k=1,2,\dots,t$ gives us $$0\ge \sum_{k=1}^t \left(\frac{b_k}{y_k}+\frac{y_k-y_{k+1}}{y_k^2}- \frac{b_{k+1}}{y_{k+1}}\right)=S-\frac{b_{t+1}}{y_{t+1}},$$ so $S\le \frac{b_{t+1}}{L}$. First, let's check if this maximum can be attained with non-negative real $x_k$. Equality holds if and only if $y_k=\frac{2y_{k+1}}{b_k+1}$ for $k=1,2,\dots,t$ (where $y_{t+1}=L>0$) - this determines the $y_k$'s starting from $y_{t+1}$ down to $y_1$. So clearly, all the $y_k$ are positive. Our goal is to show that $x_k=(y_k-y_{k+1})+k\ge 0$. However, trivial induction shows that $0\le b_n\le 1$ for all $n\ge 1$ (they are all $\ge 0$, and so $b_n\le 1$ implies $b_{n+1}=\frac14(1+b_n)^2\le \frac14(1+1)^2=1$). This means that $y_k=\frac2{b_k+1}y_{k+1}\ge y_{k+1}$, so we'll definitely have $x_k\ge 0$. Now let's notice that $b_2=\frac14$, and so $b_{n+1}=a_n$. Therefore $\max S=\frac{b_{t+1}}{L}=\frac1L a_t$, and the constant we seek is $$\lambda=\frac1{\frac{2003\cdot 2002}2+1}=\frac1{2005004}.$$
09.03.2024 02:20
We claim more generally that $\lambda=\frac{1}{B(B+1)+1}$. We have: $$\sum_{k=1}^{B}{\frac{x_{k}-k}{(x_{k}+\dots+x_{B}+\frac{k(k-1)}{2}+1)^2}}\leq \frac{a_B}{B(B+1)+1}$$We notice this becomes much simpler if we shift $x_i\mapsto i+y_i,-i\leq y_i$. The summation becomes: $$\sum_{k=1}^{B}{\frac{y_k}{(y_{k}+\dots+y_{B}+\frac{B(B+1)}{2}+1)^2}}\leq \frac{a_B}{B(B+1)+1}$$Now for $1\leq i\leq k-1$ map $y_i\mapsto (\frac{y_B+\frac{B(B+1)}{2}+1}{\frac{B(B-1)}{2}+1})z_i$ noticing $-i\leq z_i$: We have: $$\frac{\frac{B(B-1)}{2}+1}{y_B+\frac{B(B+1)}{2}+1}\sum_{k=1}^{B-1}{\frac{z_k}{(z_{k}+\dots+z_{B-1}+\frac{B(B-1)}{2}+1)^2}}+\frac{y_B}{(y_B+\frac{B(B+1)}{2}+1)^2}\leq \frac{a_B}{B(B+1)+1}$$Now applying induction with the trivial base case $B=1$: $$\frac{a_{B-1}}{y_B+\frac{B(B+1)}{2}+1}+\frac{y_B}{(y_B+\frac{B(B+1)}{2}+1)^2}\leq \frac{a_B}{B(B+1)+1}$$Taking the derivative and doing the maximum test on $[-B,\infty)$ we get that the LHS is maximized when $y_B=\frac{(\frac{B(B+1)}{2}+1)(1-a_{B-1}}{1+a_{B-1}}$ yielding: $$\frac{\frac{1}{4}(1+a_{B-1})^2}{B(B+1)+1}\leq \frac{a_B}{B(B+1)+1}$$It is also clear that the inequality is sharp finishing the question.