The answer is $0\le r\le1/2$. Claim. $r=1/2$ works, and is maximal. Proof. To achieve $r=1/2$, take $b_n=n(n+1)/2$, from which \[\frac{b_n}{n^2}=\frac{n(n+1)}{2n^2}=\frac{n+1}{2n}=\frac12+\frac1{2n},\]which clearly satisfies the problem condition. We inductively show that $b_n\le n(n+1)/2$. The base case has been given to us. Now, if the hypothesis holds for all integers less than $n$, then \[\frac{b_n}{n^2}<\frac{b_{n-1}}{(n-1)^2}\le\frac n{2(n-1)}\implies b_n<\frac{n^3}{2(n-1)}.\]It is easy to verify the largest possiblie $b_n$ is $n(n+1)/2$, as claimed. $\blacksquare$ Claim. All $r<1/2$ work. Proof. Consider the sequence $(a_n)$ defined by $a_n:=\left\lceil kn^2\right\rceil+n$. Since $a_n$ is $O(n^2)$ and $k<1/2$, there exists $N$ such that for all $n\ge N$, $a_n/n^2<1/2$. I claim the sequence \[b_n:=\begin{cases}n(n+1)/2&\text{ for }n<N\\ a_n&\text{ for }n\ge N\end{cases}\]works. By definition of $N$, $b_n/n^2>b_{n+1}/(n+1)^2$ for $n<N$, so it suffices to verify $a_n/n^2$ is strictly decreasing for $n\ge N$. In other words, we want to show that \[L:=\frac{\left\lceil kn^2\right\rceil+n}{n^2}>\frac{\left\lceil k(n+1)^2\right\rceil+n+1}{(n+1)^2}=:R\]for all $n\ge N$. Since $\left\lceil kn^2\right\rceil\ge kn^2$, \[L\ge\frac{kn^2+n}{n^2}=k+\frac1n,\]and similarly since $\left\lceil k(n+1)^2\right\rceil<k(n+1)^2+1$, \[R<\frac{k(n+1)^2+n+2}{(n+1)^2}=\frac1k+\frac{n+2}{(n+1)^2},\]so it suffices to verify that \[\frac1n\ge\frac{n+2}{(n+1)^2}\iff(n+1)^2\ge n(n+2),\]which is true. $\blacksquare$ Combining these two claims, we are done.

Sad... I essentially discovered this construction, but didn't think of replacing the initial "too large" terms with triangular numbers.

P1 The answer is $[0,\tfrac{1}{2}]$. We prove the bound first. Consider the following claim. Claim: $b_n\leq\frac{n(n+1)}{2}$ for all positive integer $n$. Proof: Induct on $n$. The base case $n=1$ is obvious. Assume that $b_{n-1}\leq\tfrac{n(n-1)}{2}$. We will prove that $b_{n}\leq\tfrac{n(n+1)}{2}$. Note that \begin{align*} b_{n} &< \frac{n^2}{(n-1)^2}\cdot\frac{n(n-1)}{2} \\ &= \frac{n^3}{2(n-1)} \\ &= \frac{n^3-n}{2(n-1)} + \frac{n}{2(n-1)} \\ &< \frac{n(n+1)}{2}+1 \end{align*}hence we are done.$\blacksquare$ The claim immediately implies the bound. Now we move on to the construction part. The equality case above $b_n=\tfrac{n(n+1)}{2}$ gives $\tfrac{1}{2}$. Now we give a sequence with converge to $L$ for $0<L<\tfrac{1}{2}$. Define $$s_n = \frac{1}{n^2} + \frac{1}{(n+1)^2} + \frac{1}{(n+2)^2} + \hdots$$Let $M$ be the smallest positive integer which $s_M<\tfrac{1}{2}-L$. We define the sequence $b_n$ by $$b_n = \begin{cases} \frac{n(n+1)}{2} & n<M^{2019} \\ \lfloor n^2(L+s_n)\rfloor & \text{otherwise.} \end{cases}$$By the condition, for large $n$ we have $$\frac{b_n}{n^2}\in \left(L+s_n+\frac{1}{n^2}, L+s_n\right] = (L+s_{n+1}, L+s_n).$$Intervals of this type are disjoint. This gives the strictly increasing. Moreover, $L<\tfrac{b_n}{n^2}\leq L+s_n$ thus the sequence $\tfrac{b_n}{n^2}$ converges to $L$ as desired.

I claim that any real numbers $0 \le r \le \frac{1}{2}$ satisfy this. Notice that as $b_n \in \mathbb{N}$, then $\frac{b_n}{n^2} \in \mathbb{Q}^+$ for every $n \in \mathbb{N}$. This proves that $r \ge 0$. To prove that $0$ is achievable, take $b_n = 1$ for all $n \in \mathbb{N}$ and we have \[ \lim_{n \to \infty} \frac{b_n}{n^2} = \lim_{n \to \infty} \frac{1}{n^2} = 0\]To prove that $r \le \frac{1}{2}$ is maximum, notice that from the problem's constraint: \[ \frac{b_{k+1}}{(k+1)^2} < \frac{b_k}{k^2} \]We'll prove by induction that $b_k \le \frac{k(k+1)}{2}$ for every $k \in \mathbb{N}$. For $k = 1$, we have $b_1 = 1$. For $k = 2$, notice that $b_2 \le 3$. Now, suppose that $b_k \le \frac{k(k+1)}{2}$ for a value $k \ge 2$. \[ b_{k+1} < \frac{(k+1)^2}{k^2} b_k \le \frac{(k+1)^3}{2k} = \frac{k^2 + 3k + 2}{2} + \frac{k + 1}{2k}\]As $\frac{k^2+3k+2}{2} \in \mathbb{N}$ and $0 < \frac{k+1}{2k} < 1$. This gives us \[ b_{k+1} \le \left \lfloor \frac{k^2 + 3k + 2}{2} + \frac{k + 1}{2k} \right \rfloor = \frac{(k+1)(k+2)}{2} \]which completes the induction. To prove that $r = \frac{1}{2}$ is achievable. Take the sequence $b_k = \frac{k(k+1)}{2}$ for all $k \in \mathbb{N}$. \[ \lim_{n \to \infty} \frac{b_n}{n^2} = \lim_{n \to \infty} \frac{n+1}{2n} = \frac{1}{2} \] It suffices to prove that for any positive reals $0 < r < \frac{1}{2}$, we can have \[ \lim_{n \to \infty} \frac{b_n}{n^2} = r \]This is possible by taking $b_n = \lceil rn^2 \rceil + n$ for some $n > N$ and $b_n = \frac{n(n+1)}{2}$, when $n \le N$. We'll first prove that such sequence satisfy. Now, we'll prove that such sequence $b_k$ satisfies \[ \frac{b_k}{k^2} > \frac{b_{k+1}}{(k+1)^2} \]By expanding, we want to prove that \[ (k+1)^2k + (k+1)^2 \lceil rk^2 \rceil > k^2(k+1) + k^2 \lceil r(k+1)^2 \rceil \]\[ k(k+1) + (k+1)^2 \lceil rk^2 \rceil > k^2 \lceil r(k+1)^2 \rceil \]But actually, \begin{align*} (k+1)^2 \lceil rk^2 \rceil &> (k+1)^2 (rk^2) \\ &= k^2 (r(k+1)^2 + 1) - k^2 \\ &> k^2 \lceil r(k+1)^2 \rceil - k^2 \end{align*}which is true. Now, we need to find a constraint for $N$. Since $b_n = \frac{n(n+1)}{2}$ for all $n \le N$. Then we have $b_{N + 1} < \frac{(N+1)(N+2)}{2}$ as well. This gives us \[ \lceil r(N+1)^2 \rceil + N + 1 < \frac{(N+1)(N+2)}{2} \]But for large enough $N$, we must have \[ \lceil r(N+1)^2 \rceil + N + 1 < r(N+1)^2 + N + 1 < \frac{1}{2} N^2 + \frac{3}{2}N + 1 \]as $r < \frac{1}{2}$. We are hence finished. Now, \[ \lim_{n \to \infty} \frac{b_n}{n^2} = \lim_{n \to \infty} \frac{\lceil rn^2 \rceil + n}{n^2} = r \]because \[ r = \lim_{n \to \infty} \frac{ rn^2 + n}{n^2} \le \lim_{n \to \infty} \frac{ \lceil rn^2 \rceil + n}{n^2} \le \lim_{n \to \infty} \frac{rn^2 + n + 1}{n^2} = r \]

We claim all $0 \leq r \leq \frac{1}{2}$ work. We first prove that all $r$ are in this range. To do so, we will prove that $b_n \leq \frac{n^2 + n}{2}$ for all $n$. We do so by induction on $n$. As the base case, we have $b_1 = 1 = \frac{1^2 + 1}{2}$. Now, suppose $b_k \leq \frac{k^2 + k}{2}$. We have \begin{align*} \frac{b_{k + 1}}{(k + 1)^2} &< \frac{b_k}{k^2} \\ &< \frac{k^2 + k}{2k^2} \\ &< \frac{k + 1}{2k} \\ b_{k + 1} &< \frac{(k + 1)^3}{2k} \\ b_{k + 1} &< \frac{k^2}{2} + \frac{3k}{2} + \frac{3}{2} + \frac{1}{2k}. \end{align*}However, note that \begin{align*} \frac{(k + 1)^2 + (k + 1)}{2} &= \frac{k^2 + 3k + 2}{2} \\ &< \frac{k^2}{2} + \frac{3k}{2} + \frac{3}{2} + \frac{1}{2k} \\ \frac{(k + 1)^2 + (k + 1)}{2} + 1 &= \frac{k^2 + 3k + 4}{2} \\ &\geq \frac{k^2}{2} + \frac{3k}{2} + \frac{3}{2}k + \frac{1}{2k}, \end{align*}which is enough to show that $b_{k + 1} \leq \frac{(k + 1)^2 + (k + 1)}{2}$, completing the induction. Hence, we have $\frac{b_n}{n^2} \leq \frac{1}{2} + \frac{1}{2n}$. As $n$ approaches infinity, the right side approaches $\frac{1}{2}$, showing that $r \leq \frac{1}{2}$. Clearly $\frac{b_n}{n^2} \geq \frac{1}{n^2}$, which approaches $0$ as $n$ approaches infinity. Hence, $r \geq 0$, showing that $0 \leq r \leq \frac{1}{2}$. We now show that all $0 < r < \frac{1}{2}$ work (we have already provided constructions for $r = 0, \frac{1}{2}$). Consider some fixed $r$, and the sequence $b_n$ for which $b_n = \frac{n^2 + n}{2}$ if $rn^2 + n < \frac{n^2 + n}{2} + 100$ (this is false for large enough $n$ since $r < \frac{1}{2}$), and $b_n = \lceil rn^2 + n \rceil$ otherwise. This sequence satisfies $b_n \leq \frac{n^2 + n}{2}$ for all $n$ (which is necessary as $\frac{n^2 + n}{2}$ is the maximum value of $b_n$). We now show that \begin{align*} \frac{b_n}{n^2} &> \frac{b_{n + 1}}{(n + 1)^2} \end{align*}for all $n$. If $b_n = \frac{n^2 + n}{2}$ and $b_{n + 1} = \frac{(n + 1)^2 + (n + 1)}{2}$ this is true (as checked above). Otherwise, if $b_n = \frac{n^2 + n} {2}$ and $b_{n + 1} = \lceil r(n + 1)^2 + (n + 1) \rceil$, this is true because we have \begin{align*} \frac{b_n}{n^2} &= \frac{\frac{n^2 + n}{2}}{n^2} \\ &> \frac{\frac{(n + 1)^2 + (n + 1)}{2}}{(n + 1)^2} \\ &> \frac{\lceil r(n + 1)^2 + (n + 1) \rceil}{(n + 1)^2} \\ &= \frac{b_{n + 1}}{(n + 1)^2}. \end{align*}Finally, suppose $b_n = \lceil rn^2 + n \rceil$ and $\lceil r(n + 1)^2 + (n + 1) \rceil$. We have \begin{align*} \frac{rn^2 + n}{n^2} &> \frac{r(n + 1)^2 + (n + 1) + 1}{(n + 1)^2} \\ \iff \frac{1}{n} &> \frac{n + 2}{(n + 1)^2} \\ \iff (n + 1)^2 &> n(n + 2), \end{align*}which is true. Thus, we have \begin{align*} \frac{\lceil rn^2 + n \rceil}{n^2} &\geq \frac{rn^2 + n}{n^2} \\ &> \frac{r(n + 1)^2 + (n + 1) + 1}{(n + 1)^2} \\ &> \frac{\lceil r(n + 1)^2 + (n + 1) \rceil}{(n + 1)^2}, \end{align*}or $\frac{b_n}{n^2} > \frac{b_{n + 1}}{(n + 1)^2}$. Thus, this sequence satisfies the given condition. As the infimum of $\frac{b_n}{n^2}$ for this sequence is $r$, we may conclude that all $0 \leq r \leq \frac{1}{2}$ are achievable, as claimed. This completes the proof.

What is the logic behind bn<n(n+1)/2? you find it by try and error or its a method yo find it?

stamatelos wrote: What is the logic behind bn<n(n+1)/2? you find it by try and error or its a method yo find it? Short answer: Trial and Error Long answer: I think this is quite intuitive. When I did this problem I first listed out values of $b_i$'s. Note that $b_1 = 1$. Then, we need $\tfrac{b_2}{4} < 1$ so the maximum possible value of $b_2$ is $3$. Then, we need $\tfrac{b_3}{9} < \tfrac34$ which yields the maximum possible value of $b_3$ is $6$. Then, we need $\tfrac{b_4}{16} < \tfrac69$ so the maximum possible value (after some computation) of $b_4$ is $10$. So the maximum possible value of the first four $b_i$'s follows the sequence $1, 3, 6, 10$. Hopefully this looks familiar. After noting the (quite obvious) pattern at this point, you should be ready to induct.

Wait, this seems similar to some CMC 10A problem...

Why does $r < 0$ not work? (i.e. what if the $b_i$'s are negative?)

arvind_r wrote: Why does $r < 0$ not work? (i.e. what if the $b_i$'s are negative?) a1267ab wrote: Choose positive integers $b_1, b_2 \dots$ Your welcome

The answer is $0 \leq r \leq 1/2$. Proof of Necessity: Choose the $(b_i)$ to be as large as possible. Now I claim that $b_n = n(n+1)/2$ for all positive integers $n$, by induction. Note that if $b_n = \frac{n(n+1)}{2}$, it remains to show that $b_{n+1} = \frac{(n+1)(n+2)}{2}$ works but $b_{n+1} = \frac{(n+1)(n+2)}{2}+1$ fails. Therefore, it suffices to show $$\frac{(n+1)(n+2)}{(n+1)^2} \leq\frac{n(n+1)}{n^2} \leq \frac{(n+1)(n+2)+2}{(n+1)^2}.$$ The left inequality expands to $n(n+2)\leq (n+1)^2$, while the right inequality expands to $(n+1)^3 \leq n(n^2+3n+4)$, or $n^3+3n^2+3n+1 \leq n^3+3n^2+4n \implies 1 \leq n$, obvious. Now obviously $\frac{b_n}{n^2} \leq \frac{n(n+1)}{2n^2} = \frac{n+1}{2n}$, so $r \leq 1/2$. Construction: It remains to show that any $r$ for $0 \leq r \leq 1/2$ is achievable for some choice of $(b_i)$. Set $b_n = \left\lceil rn^2 + n\right\rceil$ if $\frac{\left\lceil rn^2 + n\right\rceil}{n^2} < \frac{1}{2}$, and set $b_n = n(n+1)/2$ otherwise. It suffices to show that $b_n/n^2 > b_{n+1}/(n+1)^2$, as this sequence will tend towards $r$ for large $n$. One may manually check that this construction works, as desired.

The answer is $r \in [0,\tfrac{1}{2}]$. I will first prove necessity. Clearly, $r \geq 0$, so we only have to prove $r \leq \tfrac{1}{2}$. This is established with the following claim. Claim: For all $n$, we have $b_n\leq \tfrac{1}{2}n(n+1)$. Proof: Use induction on $n$, with the base case of $n=1$ being clear. Suppose now that we have $b_n \leq \tfrac{1}{2}n(n+1)$. I will show that $b_{n+1} \leq \tfrac{1}{2}n(n+1)$. We require: $$\frac{b_n}{n^2}>\frac{b_{n+1}}{(n+1)^2} \implies \frac{\tfrac{1}{2}n(n+1)}{n^2}=\frac{n+1}{2n}>\frac{b_{n+1}}{(n+1)^2}.$$From here, it's not hard to verify that all $b_{n+1} \geq \tfrac{1}{2}n(n+1)+1$ fail this requirement, thus completing the induction. This clearly implies $r\leq \tfrac{1}{2}$. It remains to provide a construction. For $r=\tfrac{1}{2}$, we can take $b_n=\tfrac{1}{2}n(n+1)$, which gives $\tfrac{b_n}{n}=\tfrac{1}{2}+\tfrac{1}{2n}$ for all $n$. This is clearly valid. Now we deal with $r<\tfrac{1}{2}$. For some arbitrary $r \in [0,\tfrac{1}{2})$, consider the sequence $(a_n)$ defined by $a_n=\lceil rn^2\rceil+n$. It is clear that for sufficiently large $n$, we have $$a_n\leq rn^2+n+1<\tfrac{1}{2}n(n+1).$$So we can take some positive integer $N$ such that for all $N\geq n$, $a_n<\tfrac{1}{2}n(n+1)$. Then define $$b_n=\begin{cases} \frac{1}{2}n(n+1)& n<N\\ a_n & n\geq N.\end{cases}$$Observe that $$\frac{b_n}{n^2}\geq \frac{a_n}{n^2}=\frac{\lceil rn^2\rceil+n}{n^2}\geq \frac{rn^2}{n^2}=r,$$so we have $\tfrac{b_n}{n^2} \geq r$ for all $n \geq 1$. Since $\lim_{n \to \infty} \tfrac{b_n}{n^2}=r$, it follows that $r$ is maximal. Hence we only have to verify that $\tfrac{b_n}{n^2}>\tfrac{b_{n+1}}{(n+1)^2}$ for all $n \geq 1$. This was already proven for all $n<N-1$ and is clear for $n=N-1$, so we only have to prove it for $n \geq N$. It suffices to show that $$\frac{a_n}{n^2}>\frac{a_{n+1}}{(n+1)^2} \iff \frac{\lceil rn^2\rceil+n}{n^2}>\frac{\lfloor r(n+1)^2\rfloor+n}{(n+1)^2}$$holds for all $n \geq N$. We have: \begin{align*} \frac{\lceil rn^2\rceil+n}{n^2}&>\frac{\lceil r(n+1)^2\rceil+(n+1)}{(n+1)^2}&&\iff\\ (n+1)^2\lceil rn^2\rceil+n(n+1)^2&>n^2\lceil r(n+1)^2\rceil +n^2(n+1)&&\iff\\ n^2+n&>n^2\lceil r(n+1)^2\rceil-(n+1)^2\lceil rn^2\rceil&&\iff\\ n^2+n&>n^2(r(n+1)^2+\{1-r(n+1)^2\})-(n+1)^2(rn^2+\{1-rn^2\})&&\iff\\ n^2+n&>n^2\{1-r(n+1)^2\}-(n+1)^2\{1-rn^2\}, \end{align*}where we use the easily verifiable identity $\lceil x \rceil=x+\{1-x\}$ to get from the third line to the fourth. Note that we have $n^2\{1-r(n+1)\}<n^2$, and $(n+1)^2\{1-rn^2\}$ must be nonnegative, so $$n^2\{1-r(n+1)^2\}-(n+1)^2\{1-rn^2\}>n^2.$$As $n^2+n>n^2$, the original inequality is true, so we indeed have $\tfrac{b_n}{n^2}>\tfrac{b_{n+1}}{(n+1)^2}$ for all $n$. Hence, this construction for $r$ works, and we're done. $\blacksquare$

为什么我无法下载这个文档，帮帮我

somewhere123 wrote: 为什么我无法下载这个文档，帮帮我 Why can't you download the document? I'm not sure what document your talking about..

a1267ab wrote: Choose positive integers $b_1, b_2, \dotsc$ satisfying \[1=\frac{b_1}{1^2} > \frac{b_2}{2^2} > \frac{b_3}{3^2} > \frac{b_4}{4^2} > \dotsb\]and let $r$ denote the largest real number satisfying $\tfrac{b_n}{n^2} \geq r$ for all positive integers $n$. What are the possible values of $r$ across all possible choices of the sequence $(b_n)$? Carl Schildkraut and Milan Haiman Posting for storage. We see that if $b_n \leq \frac{n(n+1)}{2}$, then $b_{n+1}^2 < \dfrac{(n+1)^2b_n}{n^2} \leq \frac{(n+1)^3}{2n} = \dfrac{n^3 + 3n^2 + 3n + 1}{2n} = \dfrac{(n+1)(n+2)}{2} + \frac{n+1}{2n} \implies b_{n+1} \leq \dfrac{(n+1)(n+2)}{2}$ and $b_1 = \frac{1 \cdot 2}{2}$. This means that $\frac{b_n}{n^2} \leq \frac{n+1}{2n}$ which can be $\frac{1}{2} + \epsilon$ where $\epsilon$ is an arbitrarily small positive real number. This means that $r \leq \frac{1}{2}$. We claim that all reals $r \in [0, \frac{1}{2}]$ work. Simply choose $b_n = \lceil rk^2 + k \rceil$ if $\lceil rk^2 + k \rceil < \frac{k^2}{2}$ or $b_k = \frac{k(k+1)}{2}$ otherwise. Simply because $\lceil rk^2 + k \rceil < \frac{k^2}{2}$ may not be true for all positive integers $k$. We can see that this construction indeed works.

I wonder what’s the motivation behind looking at $\lceil cn^2 \rceil +n$. Thanks a lot!

FishHeadTail wrote: I wonder what’s the motivation behind looking at $\lceil cn^2 \rceil +n$. Thanks a lot! Here's how I came up with it (might be already mentioned in the thread). We need $cn^2$ so the limit of $(b_n)$ approaches $c$. However $c$ can be any real number, so we use the ceiling. However, $b_n = \lceil{cn^2 \rceil}$ still doesn't work, so we can add a linear term, knowing that the limit is still $c$ but $\tfrac{b_n}{n^2}$ is decreasing. There is one more issue: the initial terms are too large, but this is an easy fix as we can just replace them with triangular numbers, the end.

a1267ab wrote: Choose positive integers $b_1, b_2, \dotsc$ satisfying \[1=\frac{b_1}{1^2} > \frac{b_2}{2^2} > \frac{b_3}{3^2} > \frac{b_4}{4^2} > \dotsb\]and let $r$ denote the largest real number satisfying $\tfrac{b_n}{n^2} \geq r$ for all positive integers $n$. What are the possible values of $r$ across all possible choices of the sequence $(b_n)$? Carl Schildkraut and Milan Haiman

Note $b_1=1$. We claim the answer is $\boxed{0\le r\le \frac{1}{2}}$. Part 1: Show that $r=\frac{1}{2}$ works, and that it is maximal. For $\frac{1}{2}$, set $b_n=\frac{n^2+n}{2}$, which is always an integer. So $\frac{b_n}{n^2}=\frac{1}{2}+\frac{1}{2n}$. The sequence $\frac{1}{2n}$ will converge to $0$, so $\frac{b_n}{n^2}$ will converge to $\frac{1}{2}$. Now we will show that $\frac{1}{2}$ is maximal. We will use the following claim. Claim: $\frac{b_n}{n^2}\le \frac{1}{2}+\frac{1}{2n}$, which obviously proves the first part. Proof: We will use induction. Base case(s): $n=1,2$ ($n=2$ because the maximal value for $\frac{b_2}{2^2}$ is $\frac{3}{4}=\frac{1}{2}+\frac{1}{4})$. Inductive step: Suppose $\frac{b_k}{k^2}\le \frac{1}{2}+\frac{1}{2k}\forall k<n$. Then we suppose for the sake of contradiction that $\frac{b_n}{n^2}>\frac{1}{2}+\frac{1}{2n}$. Since $b_n$ and $n$ are both positive integers, the minimum value for $\frac{b_n}{n^2}$ is $\frac{1}{2}+\frac{1}{2n}+\frac{1}{n^2}$. This gives us the inequality $\frac{1}{2}+\frac{1}{2n}+\frac{1}{n^2}<\frac{1}{2}+\frac{1}{2n-2}\implies \frac{1}{2n}+\frac{1}{n^2}=\frac{n+2}{2n^2}<\frac{1}{2n-2}$. Multiplying both sides by $2n^2$ gives $n+2<\frac{n^2}{n-1}$. Since $n>1$, multiplying both sides by $n-1$ gives $(n+2)(n-1)<n^2\implies n^2+n-2<n^2\implies n-2<0$, a contradiction as $n\ge 2$. Part 2: Show that all $0\le r<\frac{1}{2}$ work. Obviously we can set $b_i=i\forall i$, which gives $r=0$, so henceforth assume $0<r<\frac{1}{2}$. Let $N$ be a sufficiently large value so that for all $k\ge N$, $\left\lceil rk^2+k\right\rceil<\frac{k^2+k}{2}$. Let $b_k=\left\lceil rk^2+k \right\rceil\forall k\ge N$ and $b_n=\frac{n^2+n}{2}\forall k<N$. Clearly $\frac{b_k}{k^2}$ converges to $\frac{rk^2+k+c}{k^2}=r+\frac{1}{k}+\frac{c}{k^2}$, where $c<1$. Since both $\frac{1}{k}$ and $\frac{c}{k^2}$ converge to $0$, $\frac{b_k}{k^2}$ converges to $r$. It suffices to show that it's strictly decreasing. For all $n<N$, $\frac{b_n}{n^2}=\frac{1}{2}+\frac{1}{2n}$, which is strictly decreasing. We note $\frac{b_{N-1}}{(N-1)^2}=\frac{1}{2}+\frac{1}{2N-2}>\frac{1}{2}+\frac{1}{2N}>\frac{b_{N}}{N^2}$. Thus, it suffices to show that for all $k\ge N$, $\frac{b_k}{k^2}>\frac{b_{k+1}}{(k+1)^2}$. We have \[\frac{b_k}{k^2}=\frac{\left\lceil rk^2+k\right\rceil}{k^2}\ge\frac{rk^2+k}{k^2}\] Claim: $\frac{rk^2+k}{k^2}>\frac{r(k+1)^2+(k+1)+1}{(k+1)^2}$. If we have proven this, we are done as $\frac{r(k+1)^2+(k+1)+1}{(k+1)^2}>\frac{b_{k+1}}{(k+1)^2}$ Proof: AFTSOC $\frac{rk^2+k}{k^2}\le \frac{r(k+1)^2+(k+1)+1}{(k+1)^2}$. Then $r+\frac{1}{k}\le r+\frac{1}{k+1}+\frac{1}{(k+1)^2}\implies \frac{1}{k}\le \frac{1}{k+1}+\frac{1}{(k+1)^2}=\frac{k+2}{(k+1)^2}$. Multiplying both sides by $k(k+1)^2$ gives $(k+1)^2\le k(k+2)\implies k^2+2k+1\le k^2+2k$, which is absurd.

After getting the upper and lower bounds on $r$, another approach would be to pick any arbitrary value of $r$ and an arbitrarily large $k$, then set $b_k$ as the smallest integer satisfying $\frac{b_k}{k^2}>r$ and move "backward", picking the smallest fraction greater than the previous, and show that this works via contradiction.

The answer is all reals between $0$ and $\frac{1}{2}$. Upper bound is trivial by thinking. Construction is to stay on the upper bound construction until you are able to switch to $b_n = \lceil rn^2 \rceil + n$, finishing.

引理: 对于 $\forall n\in\mathbb Z_+$, 都有 $b_n\leqslant\frac 12n(n+1)$. 我们运用数学归纳法证明该引理. 由已知 $n=1$ 时结论成立. 假设对于 $n>1$, 结论对于 $n-1$ 成立, 则有 $$b_n<\frac{n^2}{(n-1)^2}b_{n-1}\leqslant\frac{n^2}{(n-1)^2}\cdot\frac 12n(n-1)=\frac{n^3}{2(n-1)}<\frac{n(n+1)}{2}+1$$结合 $b_n\in\mathbb Z$, 知 $b_n\leqslant\frac 12n(n+1)$, 归纳成立. 回到原题, 由引理知 $r\leqslant\frac{b_n}{n^2}\leqslant\frac 12+\frac 1{2n}$, 因此 $r\leqslant\frac 12$. 对于数列 $b_n=\frac 12n(n+1)$, 有 $r=\frac 12$; 对于数列 $b_n\equiv 1$, 有 $r=0$. 对于 $0<r<\frac 12$, 取 $N\in\mathbb Z_+$, 使得 $n\geq N$ 时, 都有 $\left\lceil rn^2+n\right\rceil <\frac 12n(n+1)$. 取数列 $b_n=\frac 12n(n+1)$, $1\leq n<N$; $b_n=\left\lceil rn^2+n\right\rceil$, $n\geq N$. 则 $\lim_{n\to +\infty}\frac {b_n}{n^2}=r$. 综上所述, ${r}$ 的取值范围为 $\boxed{\left[0,\frac 12\right]}$.$\blacksquare$

We claim that the answer is $0\leq r\leq 1/2.$ Claim 1: $$b_n\leq \frac{n(n+1)}{2}.$$We will use induction. Clearly, this is true for $n=1,2,3.$ We will use induction. Suppose that $$b_k\leq \frac{k(k+1)}{2}$$for some $k\geq 3$. Then, $$b_{k+1}<b_k\frac{(k+1)^2}{k^2}\leq \frac{(k+1)^3}{2k}.$$ Case 1: $k$ is even. Then, $$\frac{(k+1)^3}{2k}=\frac{k^2}{2}+\frac{3k}{2}+\frac{3}{2}+\frac{1}{2k}.$$The first two terms will be integers if $k\geq 3$ and $k$ is even, so its floor is $$\frac{k^2}{2}+\frac{3k}{2}+1=\frac{(k+1)(k+2)}{2},$$and since $$b_{k+1}\leq \lfloor \frac{(k+1)^3}{2k}\rfloor,$$this case is resolved. Case 2: $k$ is odd. Then, let $k=2s-1$, so $$b_{k+1}\leq \lfloor \frac{(k+1)^3}{2k}\rfloor =\lfloor \frac{4s^3}{2s-1}\rfloor=\lfloor 2s^2+s+\frac{1}{2}+\frac{1}{4s-2}\rfloor=2s^2+s,$$which is what we want. Hence, we have shown the claim. This clearly shows that $r\leq 1/2$. It also shows that $r=1/2$ is achievable since we can just set $b_n=\frac{n(n+1)}{2}.$ Clearly, $r\geq 0$. Furthermore, $r=0$ achievable by $b_n=1$. It remains to show that $0<r<1/2$ is achievable. Claim 2: If $0<r<1/2$ is a real number, then $$\frac{\lceil rn^2 \rceil +n}{n^2}$$is decreasing with respect to $n$ when $n$ is a positive integer. This is just showing that $$\frac{\lceil rn^2 \rceil +n}{n^2}>\frac{\lceil r(n+1)^2 \rceil +n+1}{(n+1)^2}.$$Note that we have $$\lceil rn^2 \rceil\geq rn^2$$and $$\lceil r(n+1)^2\rceil < r(n+1)^2+1,$$so it suffices to show that $$\frac{rn^2 +n}{n^2}>\frac{r(n+1)^2+1 +n+1}{(n+1)^2}.$$This is just $$\frac{1}{n}>\frac{n+2}{(n+1)^2}$$$$(n+1)^2>n(n+2),$$which is clearly true. Note that $$\lim_{n\rightarrow \infty}\frac{\lceil rn^2 \rceil +n}{n^2}=r,$$and furthermore, $$\frac{\lceil rn^2 \rceil +n}{n^2}>r$$for all $n$. Thus, if $r<1/2$, we can first do $b_n= \frac{n(n+1)}{2}$ for sufficiently many terms, and then swap over to $$b_n=\frac{\lceil rn^2 \rceil +n}{n^2}$$and do that for the rest of the way to achieve $r$ (this works if we go sufficiently far since it goes from larger to 1/2 to below 1/2 during the transition if we wait sufficiently long, since it heads towards $r<1/2$), so we are done.

Obviously $r \ge 0$, with equality achievable by $b_i = 1$ for all $i$. Similarly, note that $r \le \frac{1}{2}$. To see this, we can imagine starting with $b_1 = 1$ and greedily picking the largest possible $b_2,b_3,\ldots$. It's clear this greedy strategy will give the largest possible $r$. Using this greedy method, induction shows that $b_n = {{n+1} \choose 2}$ for all $n \ge 1$. Then taking $\lim_{n \to \infty} \frac{b_n}{n^2} = \frac{1}{2}$ finishes. Furthermore, this implies $b_n \le {{n+1} \choose 2}$ for any sequence $b_i$. Claim: All $r \in \left[0,\frac{1}{2}\right]$ are achievable. Proof: We've already shown $0$ and $\frac{1}{2}$ are achievable. Consider $a_n = \left \lceil{rn^2}\right \rceil+n$. Clearly, $\lim_{n \to \infty} \frac{a_n}{n^2} = r$. We claim that \begin{align*} b_n &= {{n+1} \choose 2} \text{ for $n \le N$} \\ b_n &= \left \lceil{rn^2}\right \rceil+n \text{ else} \end{align*}for some sufficiently large $N$ works as a sequence. First, to determine $N$, just take any $n$ such that \[\frac{1}{1-2r} < \frac{n^2}{n+2} \text{ which implies } \left \lceil{rn^2}\right \rceil+n < \text{max $b_n$} = {{n+1} \choose 2}\]Secondly, it's not hard to verify that, when $n>N$, the sequence $\frac{b_n}{n^2}$ is decreasing as desired. Thus since these two conditions are met, this sequence $b_n$ works, and we're done. $\square$ Remark: The actually checking of the inequality is omitted as it's not difficult or useful. However, a small note: to actually verify the inequalities, use $\left \lceil{x}\right \rceil \ge x$ and $ x+1 \ge \left \lceil{x}\right \rceil$.

Note that $b_i = 1$. We have that for $j > i$ \[ b_{j} \le \left\lfloor \frac{(j)^2}{i^2} \cdot b_j \right\rfloor \]Note that the inequality is the tightest when $j = i + 1$ Consider the maximal possible value of $r$, which occurs when equality holds between $i, j = i + 1$. We claim that this value is $\frac{1}{2}$. We have that \[ b_{i+1} = \left\lfloor \frac{(i+1)^2}{i^2} \cdot b_i \right\rfloor = b_i + \left\lfloor \frac{2}{i} b_i \right\rfloor \]Thus, if $i \mid 2b_i$, then $b_{i+1} = \frac{i + 2}{i}b_i$. Since $b_1 = 1$, we can inductively solve to get $b_2 = 3$, $b_3 = 6$, $b_n = \frac{n(n+1)}{2}$ and as $n \to \infty$, $\frac{b_n}{n^2} \to \frac{1}{2}$. Claim: If $r$ is the maximal for a fixed $b_i$, then $\frac{b_i}{i^2} - r \le C_j = \sum_{j=i}^{\infty} \frac{1}{j^2}$ Proof. Take $b_{i+1}$ as maximal, repeat to get a decrease of at most $C_j$. $\blacksquare$ Now, define $b_i$ inductively as maximal values such that $\frac{b_i}{i^2} < \frac{b_{i-1}}{(i-1)^2}$, jumping down to $b_i = \left\lceil i^2 (r + C_i) \right\rceil$ whenever $\frac{b_{i-1}}{(i-1)^2} > \frac{1}{i-1} + r + C_i$.

We claim that the only real constants $r$ for which such a sequence of positive integers exist are $0 \le r \le \frac{1}{2}$. We start off with proving the bound. It is not hard to see that $r \ge 0$ since all the terms of the form $\frac{b_i}{i^2}$ are strictly positive. For the upper bound, we first note that, $b_1=1$. Further, we can show the following result via induction. Claim : For all positive integers $i \ge 2$, \[\frac{b_i}{i^2}\le \frac{i+1}{2i}\] Since $b_1=1$ and $\frac{b_2}{4} < 1$ we have $b_2 <4$ and thus, $b_2 \le 3$ implying $\frac{b_2}{4} \le \frac{3}{4}$ as desired. Now, we assume that for some positive integer $k \ge 2$, $\frac{b_k}{k^2} \le \frac{k+1}{2k}$. Then, \begin{align*} \frac{b_{k+1}}{(k+1)^2} & < \frac{b_k}{k^2} \\ b_{k+1} & < \frac{(k+1)^3}{2k}\\ b_{k+1} & \ge \frac{(k+1)^3-1}{2k}\\ &= \frac{(k+1)^2+(k+1)+1}{2}\\ b_{k+1} & \ge \frac{k^2+3k+2}{2}\\ &= \frac{(k+1)(k+2)}{2} \end{align*}using the fact that $b_{k+1} \in \mathbb{N}$. Thus, $b_{k+1} \le \frac{(k+1)(k+2)}{2}$ from which it follows that, $\frac{b_{k+1}}{(k+1)^2} \le \frac{k+2}{2(k+1)}$ completing the induction. Now, if $r>\frac{1}{2}$, there must exist some $\epsilon >0$ and $k \in \mathbb{N}$ such that for all $i \ge k$, $b_i \ge \frac{1}{2} + \epsilon$. But now, considering $i > \frac{1}{2\epsilon}$ contradicts the above claim, which finishes the proof of the bound. All that remains now is to provide a construction. When $r=0$ and $r=\frac{1}{2}$ simply consider the sequences $b_i=i$ and $b_i = \frac{i(i+1)}{2}$ respectively. For all $0 < r < \frac{1}{2}$ we can consider the sequence, \[b_i= \begin{cases} \frac{i(i+1)}{2} & i < N\\ \lceil ri^2+i \rceil & i \ge N \end{cases}\]for sufficiently large $N$. To see why this works we let $c_i = \frac{b_i}{i^2}$ for all positive integers $i$, it is first clear that $c_1=1$ and $c_i$ is increasing for $1 \le i < \frac{3}{1-2r}$. Then, we have two consecutive terms of the form, \[c_{k-1} = \frac{k}{2(k-1)} \text{ and } c_k = \frac{\lceil rk^2+k \rceil}{k^2}\]Note that, \begin{align*} c_k & = \frac{\lceil rk^2+k \rceil}{k^2} \\ & \le \frac{rk^2+k+1}{k^2}\\ & < \frac{k}{2(k-1)}\\ &= c_{k-1} \end{align*}for sufficiently large $k$ (so we simply need to select $N$ such that the final inequality holds). Further, for all $i>k$, $c_i$ is also increasing since, \begin{align*} \frac{\lceil ri^2+i \rceil}{i^2} & > \frac{ri^2 +i}{i^2}\\ & = r + \frac{1}{i}\\ & > r + \frac{i+2}{(i+1)^2}\\ & > \frac{r(i+1)^2 + (i+1) + 1}{(i+1)^2}\\ & > \frac{\lceil r(i+1)^2+ (i+1) \rceil}{(i+1)^2} \end{align*}Thus, the described sequence satisfies all the desired characteristics. Further, \[\frac{b_n}{n^2} = \frac{\lceil rn^2+n \rceil}{n^2}> r\]So, $r$ is a lower bound of $c_i$. To see why it is the greatest lower bound, say there exists some $\epsilon >0$ and $k \in \mathbb{N}$ such that for all $ i \ge k$ we have $c_i \ge r+ \epsilon$. Then, we have $\frac{\lceil ri^2+i \rceil}{i^2} > r + \epsilon$ so, \begin{align*} ri^2+i+1 & > \lceil ri^2+i \rceil > ri^2 + i^2 \epsilon\\ i+1 & > i^2 \epsilon \end{align*}which is clearly false for sufficiently large $i$. Thus, $r$ is in fact the greatest lower bound of $c_i$ which completes the solution.

USA 2020 TST p1 We claim that $r \in [0,1/2]$. We start off with the following claim. Claim : $b_n \leq \frac{n(n+1)}{2}$ for all $n$. Proof: We use induction, base case being $n=1$ is trivial. First assume that $b_{n-1} \leq \frac{n(n-1)}{2}$, we show that $b_n \leq \frac{n(n+1)}{2}$. \begin{align*} b_{n} &<\frac{n(n-1)}{2}\cdot\frac{n^2}{(n-1)^2} \\ &= \frac{n^3-n}{2(n-1)} + \frac{n}{2(n-1)} \\ &< \frac{n(n+1)}{2}+1 \end{align*}As desired. $\blacksquare$ Now as $n \to \infty$ we get that \[\frac{b_n}{n^2} \leq \frac{1}{2}\]. Now we give a construction of our bound. Construction: Let $b_n = \left\lceil rn^2 + n\right\rceil$ if $\frac{\left\lceil rn^2 + n\right\rceil}{n^2} < \frac{1}{2}$, otherwise, let $b_n=\frac{n(n+1)}{2}$ . Which works, hence we are done.

The answer is $r \in [0, \tfrac{1}{2} ]$. Claim: We have $b_i \leq \tfrac{i(i+1)}{2}$. Proof: We prove this with induction, with the base case of $i=1$ being obvious. For $i > 1$, we have \[b_i < \frac{i^2}{(i-1)^2} \cdot b_{i-1} \leq \frac{i^3}{2(i-1)} < \frac{i^2 + i + 2}{2},\]and since $\tfrac{i^2 + i + 1}{2}$ is not an integer, it follows that $b_i \leq \tfrac{i(i+1)}{2}$, as claimed. So, we must have $r \leq \tfrac{1}{2}$. We now show that we can obtain every $r$ in this range. Note that the value of $\tfrac{b_i}{i^2}$ decreases by at most $\tfrac{1}{i^2}$ each time we increment $i$ by one. Therefore, if we define \[f(n) := \sum_{j=n}^\infty \frac{1}{j^2},\]we can always make our sequence converge to some real number at least $L_n = \tfrac{b_n}{n^2} - f(n+1)$. Now, we construct our sequence $b_i$ as follows: for each $i$, first, set each $b_i$ to be as large as possible until $L_i$ is greater than $r$ – this must eventually happen since $\lim_{i \to \infty} f(i) = 0$. Let the $i$-value at which this happens be $k$. We continue to increase $i$, making $b_i$ as large as possible – as we do so, the value of $L_i$ increases. We repeat this until $\tfrac{1}{i^2} < (L_k - r)/2$. (Note the $k$ subscript.) Next, instead of picking $b_i$ to be as large as possible, we first set it to its maximum value and then decrease it by $1$ until $L_i$ lies in the range $(r, (r+L_k)/2)$. (This is possible since, by assumption, $\tfrac{1}{i^2} < (L_k - r)/2$.) Now, we reset $k$ to be the current value of $i$ and repeat this process indefinitely. By doing this, $L_i - r$ approaches $0$, and since $\tfrac{b_i}{i^2} - L_i$ also approaches $0$, it follows that $\tfrac{b_i}{i^2}$ approaches $r$, as desired.

$ $

In order to find the maximum possible value for $r$, we need to try maximizing each value in the sequence. Claim. $b_n$ must be the $n^\text{th}$ triangular number in order for the fraction to be maximized. Proof. This can be proven using induction with our base cases being $b_1 = 1$ and $b_2 = 1+2 = 3$. With our inductive hypothesis, assume that $b_n = \frac{n(n+1)}{2}$. Using the condition given in the problem, $b_{n+1}$ must satisfy \[ \frac{\frac{n(n+1)}{2}}{n^2} > \frac{b_{n+1}}{(n+1)^2} \]It can be easily verified that the inequality holds for $b_{n+1} = \frac{(n+1)(n+2)}{2}$. Now all there is left to show is that the condition doesn't hold up when $b_{n+1} = \frac{(n+1)(n+2)}{2}+1$. This can be shown with \begin{align*} \frac{n+1}{2n} &> \frac{\frac{(n+1)(n+2)}{2}+1}{(n+1)^2}\\ \frac{n+1}{2n} &> \frac{n^2+3n+2+2}{2(n+1)^2}\\ (n+1)^3 &> n^3 + 3n^2 + 4n \end{align*}which is false since the statement simplifies to $1>n$ which is absurd. $\blacksquare$ Since $r$ is maximized when $b_n = \frac{n(n+1)}{2}$, we have that \[ r \le \frac{n+1}{2n} \]for all $n$. As $n$ approaches infinity, we can conclude that $r \le \frac{1}{2}$. Since obviously $r\ge 0$, $r$ must lie in the interval $\left[0, \frac{1}{2}\right]$. The construction for any $r$ in this interval is done by defining \[ b_n = \begin{cases} \frac{n(n+1)}{2} & \text{if } n \le N \\ \bigl{\lceil}rn^2 + n\bigl{\rceil} & \text{if } n > N \end{cases} \]for a sufficiently large $N$ satisfying $\frac{N(N+1)}{2} > \bigl{\lceil}rN^2 + N\bigl{\rceil} $. Lastly, since \begin{align*} \frac{\left\lceil rn^2 + n \right\rceil}{n^2} &\ge r + \frac{1}{n} > r + \frac{n+2}{(n+1)^2} = \frac{\left(r(n+1)^2 + (n+1)\right) + 1}{(n+1)^2} > \frac{\left\lceil r(n+1)^2 + (n+1) \right\rceil}{(n+1)^2} \end{align*}we see that the condition $b_{n+1}>b_n$ still holds even for $n > N$ and the sequence approaches $r$ as $n$ tends to infinity. $\blacksquare$