Infimum of decreasing sequence b_n/n^2

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Infimum of decreasing sequence b_n/n^2

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USA Winter TST for IMO 2020, Problem 1 and TST for EGMO 2020, Problem 3, by Carl Schildkraut and Milan Haiman

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

223 posts

#1 h Dec 16, 2019, 5:08 PM • 5 Y

Y by centslordm, Pluto1708, megarnie, Adventure10, kub-inst

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

This post has been edited 3 times. Last edited by a1267ab, Dec 16, 2019, 6:11 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1740 posts

#2 h Dec 16, 2019, 5:42 PM • 9 Y

Y by Idio-logy, Williamgolly, Doxuantrong, ashrith9sagar_1, CALCMAN, centslordm, Pluto1708, Adventure10, MS_asdfgzxcvb

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.

This post has been edited 1 time. Last edited by TheUltimate123, Dec 16, 2019, 5:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

538 posts

#3 h Dec 16, 2019, 5:52 PM • 3 Y

Y by pad, centslordm, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1117 posts

jeff10

#4 h Dec 16, 2019, 8:19 PM • 2 Y

Y by centslordm, Adventure10

Another Construction

This post has been edited 1 time. Last edited by jeff10, Dec 16, 2019, 8:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1595 posts

#5 h Dec 16, 2019, 11:21 PM • 6 Y

Y by Mathphile01, SpecialBeing2017, MintTea, centslordm, Adventure10, Mango247

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.

This post has been edited 1 time. Last edited by MarkBcc168, Dec 17, 2019, 10:50 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

691 posts

#6 h Dec 17, 2019, 10:13 AM • 4 Y

Y by FISHMJ25, MintTea, centslordm, Adventure10

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$
Motivation

This post has been edited 1 time. Last edited by IndoMathXdZ, Dec 17, 2019, 10:14 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#8 h Jan 22, 2020, 6:42 AM • 3 Y

Y by centslordm, 554183, Adventure10

Solution

Remarks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

830 posts

niyu

#9 h Mar 15, 2020, 11:55 PM • 2 Y

Y by surferdude11, centslordm

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

#10 h Jun 29, 2020, 7:59 PM • 2 Y

Y by centslordm, Mango247

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

This post has been edited 2 times. Last edited by stamatelos, Jun 29, 2020, 8:00 PM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2726 posts

#11 h Jun 29, 2020, 8:03 PM • 3 Y

Y by centslordm, Mango247, Mango247

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.

This post has been edited 4 times. Last edited by jj_ca888, Jun 29, 2020, 8:06 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1631 posts

#13 h Jun 29, 2020, 10:36 PM • 1 Y

Y by centslordm

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

136 posts

#14 h Jul 3, 2020, 3:12 PM • 1 Y

Y by centslordm

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1063 posts

#15 h Jul 3, 2020, 3:38 PM • 3 Y

Y by cosmicgenius, arvind_r, centslordm

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1051 posts

#16 h Jan 12, 2021, 3:48 AM • 2 Y

Y by centslordm, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#17 h May 30, 2021, 2:59 PM • 1 Y

Y by centslordm

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$

This post has been edited 1 time. Last edited by IAmTheHazard, Jun 7, 2021, 6:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#18 h Jun 9, 2021, 3:48 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1506 posts

#19 h Jun 9, 2021, 4:00 AM

Y by

somewhere123 wrote:

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

Why can't you download the document?

I'm not sure what document your talking about..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1040 posts

508669

#20 h Aug 25, 2021, 2:02 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

75 posts

#21 h Aug 27, 2021, 1:51 AM

Y by

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

This post has been edited 3 times. Last edited by FishHeadTail, Sep 2, 2021, 2:07 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1051 posts

#22 h Sep 5, 2021, 1:27 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

guillermo.dinamarca

1 post

guillermo.dinamarca

#23 h Oct 31, 2021, 5:04 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5606 posts

#24 h Dec 28, 2021, 8:22 PM

Y by

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.

This post has been edited 1 time. Last edited by megarnie, Dec 28, 2021, 8:23 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7585 posts

#25 h Jan 15, 2022, 3:43 PM

Y by

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.

This post has been edited 2 times. Last edited by asdf334, Jan 15, 2022, 3:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1455 posts

#26 h Oct 27, 2022, 10:02 PM

Y by

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.

This post has been edited 1 time. Last edited by Inconsistent, Oct 27, 2022, 10:03 PM
Reason: edit

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

864 posts

#27 h Apr 2, 2023, 2:18 AM

Y by

引理: 对于 $\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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4187 posts

#29 h May 21, 2023, 9:29 PM

Y by

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.

This post has been edited 1 time. Last edited by john0512, May 21, 2023, 9:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

331 posts

#31 h Feb 6, 2024, 5:25 AM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#32 h Feb 27, 2024, 4:32 PM

Y by

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

625 posts

cursed_tangent1434

#33 h Jul 4, 2024, 5:46 AM • 1 Y

Y by GeoKing

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.

This post has been edited 1 time. Last edited by cursed_tangent1434, Jul 4, 2024, 5:48 AM
Reason: typoes

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

139 posts

Ywgh1

#34 h Aug 14, 2024, 8:04 PM

Y by

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.

This post has been edited 5 times. Last edited by Ywgh1, Aug 15, 2024, 7:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3446 posts

#35 h Aug 29, 2024, 4:12 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

757 posts

#36 h Sep 10, 2024, 3:38 AM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Trasher_Cheeser12321

13 posts

Trasher_Cheeser12321

#37 h Dec 26, 2024, 9:25 AM

Y by

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$

This post has been edited 2 times. Last edited by Trasher_Cheeser12321, Dec 26, 2024, 5:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

163 posts

aliz

#38 h Mar 27, 2025, 5:14 AM

Y by

The answer is $\boxed{0 \le r \le \frac{1}{2}}$ . Since $\frac{b_n}{n^2} \ge 0$ , $r \ge 0$ .

Claim: $b_n \le \frac{n(n+1)}{2}$
Proof: We will prove by induction. This is obvious for $n = 1$ . If it holds true for $n = k$ and not $n = k+1$ , then $\frac{\frac{k(k+1)}{2}}{k^2} \ge \frac{b_k}{k^2} > \frac{b_{k+1}}{(k+1)^2}$ so $\frac{(k+1)^3}{2k} > b_{k+1}$ . Since we assume the claim does not hold for $n = k+1$ , $b_{k+1} \ge \frac{k^2+3k+4}{2}$ . Plugging this into $b_{k+1}$ and simplifying yields $k < 1$ , contradiction.

Therefore $b_{k+1} \le \frac{(k+1)(k+2)}{2}$ , and notice that if the two are equal, then $\frac{\frac{k(k+1)}{2}}{k^2} > \frac{\frac{(k+1)(k+2)}{2}}{(k+1)^2}.$ This simplifies to $1 > 0$ which is obviously true.

Since $\frac{b_k}{k^2} \le \frac{\frac{k(k+1)}{2}}{k^2} = \frac{1}{2} + \frac{1}{2k}$ , $r$ is at max $\frac{1}{2}$ . Now consider $0 \le r < 1/2$ .

Claim: $\frac{b_n}{n^2} - r \le \frac{1}{n}$ .
Proof: Let $b_{n+1}$ be the maximum integer such that $\frac{b_n}{n^2} > \frac{b_{n+1}}{(n+1)^2}$ , so $\frac{b_{n+1} + 1}{(n+1)^2} \ge \frac{b_n}{n^2}$ . Rearranging, $\frac{b_n}{n^2} - \frac{b_{n+1}}{(n+1)^2} \le \frac{1}{(n+1)^2} < \frac{1}{(n)(n+1)} = \frac{1}{n} - \frac{1}{n+1}.$ Noticing the telescoping sum, we put $\frac{b_n}{n^2} - r \le \sum_{p=n}^{\infty} \frac{1}{p} - \frac{1}{p+1} = \frac{1}{n}.$
Now consider the construction where $b_1 = 1$ and for $k > 1$ , $b_k$ is the minimum positive integer value such that $\frac{b_k}{k^2} - r \ge \frac{1}{k}$ . Since $\frac{b_k - 1}{k^2} - r < \frac{1}{k}, \frac{b_k}{k^2} - r < \frac{1}{k} + \frac{1}{k^2}$ so if this sequence exists, it converges to $r$ .

Also, $\left( \frac{b_{k+1}}{(k+1)^2} - \frac{b_k}{k^2} \right) + \left( \frac{b_k}{k^2} - r \right) \ge \frac{1}{n} - \left( \frac{1}{n} - \frac{1}{n+1} \right) = \frac{1}{n+1}$ so since a value of $b_{k+1}$ can be found and it must be a positive (bounded from below) integer, we can find a minimum value of $b_{k+1}$ . Therefore this creates a valid sequence.

Therefore all values $0 \le r \le \frac{1}{2}$ can be possible infimums and all other values are impossible.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

353 posts

#39 h Apr 28, 2025, 2:12 AM

Y by

We claim the answer is $0 \le r \le \dfrac{1}{2}$ , the lower bound is obvious.

$\textbf{Claim 1:}$ $r \le \dfrac{1}{2}$ and is precisely the maxima.

We greedily choose $b_k$ according to the recurrence $b_{k + 1} = \left\lfloor \dfrac{(k + 1)^2}{k^2} b_k \right\rfloor$ . We will show that in fact, $b_n = \dfrac{n(n + 1)}{2}$ by induction.

The base case is obvious, now assuming up to an arbitrary $n$ to show for $n + 1$ we require
$\dfrac{(n + 1)(n + 2)}{2} = \left \lfloor \dfrac{(n + 1)^3}{2n} \right \rfloor \iff \dfrac{(n + 1)(n + 2)}{2} \le \dfrac{(n + 1)^3}{2n} < \dfrac{(n + 1)(n + 2)}{2} + 1.$ Expanding gives $n^3 + 3n^2 + 2n \le n^3 + 3n^2 + 3n + 1 < n^3 + 3n^2 + 4n$ which is true.

Now $\dfrac{b_n}{n^2} = \dfrac{1}{2} + \dfrac{1}{2n}$ which obviously approaches $\dfrac{1}{2}$ as $n$ grows large.

$\textbf{Claim 2:}$ All values $0 \le r \le \dfrac{1}{2}$ are obtainable.

Consider the sequence $b_n = \dfrac{n(n + 1)}{2}$ for $n \le K - 1$ and $b_n = \lceil rn^2 \rceil + n$ for $n \ge K$ where $K$ is sufficiently large enough such that $\dfrac{b_n}{n^2} > r$ . We claim that this construction works. Indeed,
$r < \dfrac{\lceil rn^2 \rceil + n}{n^2} < \dfrac{rn^2 + n + 1}{n^2} = r + \dfrac{1}{n} + \dfrac{1}{n^2}$ so $\lim_{n \to \infty} \dfrac{b_n}{n^2} = r$ . Moreover,
$\dfrac{\lceil rn^2 \rceil + n}{n^2} > \dfrac{\lceil r(n + 1)^2 \rceil + (n + 1)}{(n + 1)^2} \iff (n + 1)^2 \lceil rn^2 \rceil + n^2 + n > n^2 \lceil r(n + 1)^2 \rceil .$

Attachments:

This post has been edited 1 time. Last edited by blueprimes, May 4, 2025, 2:37 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

795 posts

#40 h May 6, 2025, 3:38 AM

Y by

Our answer is $\boxed{[0,\tfrac 12]}$ , constructed with $b_n = 1$ and $b_n = \tfrac{n(n+1)}{2}$ , which can be easily shown to be the extremes.

For the values in between, it suffices to find an expression of the form
$\frac{b_n}{n^2} = \frac{\lceil rn^2+sn+t \rceil}{n^2}$
for sufficiently high $n$ (where we just set $b_n = \tfrac{n(n+1)}{2}$ before that), which asymptotically approaches $r$ from above. It suffices to have
$\frac{\lceil rn^2+sn+t \rceil}{n^2} > \frac{\lceil r(n+1)^2+s(n+1)+t \rceil}{(n+1)^2},$
which suffices to have
$\frac{rn^2+sn+t}{n^2} > \frac{r(n+1)^2+s(n+1)+t+1}{(n+1)^2}$ $s(n^2+n) + t(2t+1) > n^2.$
Setting $s=1$ and $t=0$ works. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a