For each real number $x$, let $\lfloor x \rfloor$ denote the largest integer not exceeding $x$. A sequence $\{a_n \}_{n=1}^{\infty}$ is defined by $a_n = \frac{1}{4^{\lfloor -\log_4 n \rfloor}}, \forall n \geq 1.$ Let $b_n = \frac{1}{n^2} \left( \sum_{k=1}^n a_k - \frac{1}{a_1+a_2} \right), \forall n \geq 1.$ a) Find a polynomial $P(x)$ with real coefficients such that $b_n = P \left( \frac{a_n}{n} \right), \forall n \geq 1$. b) Prove that there exists a strictly increasing sequence $\{n_k \}_{k=1}^{\infty}$ of positive integers such that $$\lim_{k \to \infty} b_{n_k} = \frac{2024}{2025}.$$
Problem
Source: 2024 Vietnam National Olympiad - Problem 1
Tags: algebra, polynomial
wassupevery1
05.01.2024 11:30
Pretty nice and not too hard, suitable for P1 even though the statement looks horrible.
The polynomial we need to find is $P(x) = \boxed{-\frac{1}{5}x^2+x}$.
To prove this, first we note that, if an integer $l$ is such that $4^l < i \leq 4^{l+1}$, then $$-(l+1) \leq \log_4 i < -l \Rightarrow a_i = \frac{1}{4^{-(l+1)}} = 4^{l+1}.$$Now let $n \geq 2$ be a positive integer. Let $k$ be the unique positive integer such that $4^k < n \leq 4^{k+1}$. Then
\begin{align*}
b_n &= \frac{1}{n^2} \left( \sum_{i=1}^{4^k} a_i +\sum_{i=4^{k}+1}^{n} a_i - \frac{1}{5} \right) \\
&= \frac{1}{n^2} \left( \left( 1+(4-1) \cdot 4 + (16-4) \cdot 4^2 + \ldots + (4^k-4^{k-1}) \cdot 4^k \right) +(n-4^k) \cdot 4^{k+1} - \frac{1}{5} \right)\\
&= \frac{1}{n^2} \left( \left( 1+3 \cdot (4 + 4^1 \cdot 4^2 + \ldots + 4^{k-1} \cdot 4^k) \right) +(n-4^k) \cdot 4^{k+1} - \frac{1}{5} \right)\\
&= \frac{1}{n^2} \left( \left( 1+3 \cdot 4 \cdot \frac{4^{2k}-1}{4^2-1} \right) +(n-4^k) \cdot 4^{k+1} - \frac{1}{5} \right) \\
&= \frac{1}{n^2} \left( \left( 1+\frac{4^{2k+1}-4}{5} \right) +(n-4^k) \cdot 4^{k+1} - \frac{1}{5} \right) \\
&= \frac{1}{n^2} \left( \frac{4^{2k+1}}{5} +n\cdot 4^{k+1} - 4^{2k+1 }\right) \\
&= \frac{1}{n^2} \left(- \frac{4^{2k+2}}{5} +n\cdot 4^{k+1}\right) \\
&= \frac{1}{n^2} \left(- \frac{a_n^2}{5} +n\cdot a_n\right) \\
&= P \left( \frac{a_n}{n} \right).
\end{align*}
b) Let $\epsilon$ be a positive zero of $-\frac{1}{5}x^2+x=\frac{2024}{2025}$.
Since $\frac{2024}{2025}$ lies in the intervals $(P(1), P(2)), (P(4), P(3))$, we choose the one such that $1 < \epsilon < 2$.
Now, define the sequence $(n_k)$ such that $n_k = \left\lfloor \frac{4^{k+1}}{\epsilon} \right\rfloor$ for all $k \geq 1$.
Since $1 < \epsilon < 2$, it follows that $4^k < n_k < 4^{k+1}$, hence $a_{n_k} = 4^{k+1}$. It is trivial to see that this sequence consists of positive integers and is increasing.
Now, $\frac{4^{k+1}}{\epsilon} \leq n_k < \frac{4^{k+1}}{\epsilon} + 1$ implies $\frac{4^{k+1}}{\frac{4^{k+1}}{\epsilon} + 1} < \frac{a_{n_k}}{n_k} \leq \epsilon.$
However, note that $\lim_{k \to \infty} \frac{4^{k+1}}{\frac{4^{k+1}}{\epsilon} + 1} = \epsilon$, it follows by squeeze theorem that $\lim_{k \to \infty} \frac{a_{n_k}}{n_k} = \epsilon$, and hence from part a, $$\lim_{k \to \infty} b_{n_k} = \lim_{k \to \infty} f \left( \frac{a_{n_k}}{n_k} \right) = f(\epsilon) = \frac{2024}{2025}.$$