Let $\{a_n\}$ be a nonnegative real sequence. Define $$X_k = \sum_{i=1}^{2^k}a_i, Y_k = \sum_{i=1}^{2^k}\left\lfloor \frac{2^k}{i}\right\rfloor a_i, k=0,1,2,...$$Prove that $X_n\le Y_n - \sum_{i=0}^{n-1} Y_i \le \sum_{i=0}^n X_i$ for all positive integer $n$. Here $\lfloor\alpha\rfloor$ denotes the largest integer that does not exceed $\alpha$.
Problem
Source: 2018 China Southeast MO Grade 10 P5
Tags: algebra
NikoIsLife
31.07.2018 08:23
Let $k$ be any integer such that $2^m<k\leq 2^{m+1}$. The coefficient of $a_k$ in $X_n$ is equal to $1$. The coefficient of $a_k$ in $Y_n-\sum_{i=0}^{n-1}Y_i$ is equal to $\left\lfloor\frac{2^n}{k}\right\rfloor-\sum_{i=m+1}^{n-1}\left\lfloor\frac{2^{i}}{k}\right\rfloor$. The coefficient of $a_k$ in $\sum_{i=0}^n$ is equal to $n-m$. Now, it suffices to show that for all positive integers $k\leq 2^n$: $$1\leq\left\lfloor\frac{2^n}{k}\right\rfloor-\sum_{i=m+1}^{n-1}\left\lfloor\frac{2^{i}}{k}\right\rfloor\leq n-m$$
TacH
31.07.2018 20:13
Just use induction, base case is trivial It suffices to prove that $X_{n+1} - X_n \leq Y_{n+1}-2Y_n \leq X_{n+1}$ since, $Y_{n+1}-2Y_n = \sum_{i=1}^{2^{n+1}}\left\lfloor \frac{2^{n+1}}{i}\right\rfloor a_i, - 2 \cdot \sum_{i=1}^{2^{n}}\left\lfloor \frac{2^{n}}{i}\right\rfloor a_i,$ just note that $\left\lfloor \frac{2^{n+1}}{i}\right\rfloor - 2\cdot \left\lfloor \frac{2^{n}}{i}\right\rfloor \in {{0,1}}$ This finishes the prove