Upper bound on products in sequence

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

Upper bound on products in sequence

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: TSTST 2024, problem 7

The post below has been deleted. Click to close.

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

71 posts

#1 h Jun 24, 2024, 6:41 PM

Y by

An infinite sequence $a_1$ , $a_2$ , $a_3$ , $\ldots$ of real numbers satisfies
$a_{2n-1} + a_{2n} > a_{2n+1} + a_{2n+2} \qquad \mbox{and} \qquad a_{2n} + a_{2n+1} < a_{2n+2} + a_{2n+3}$ for every positive integer $n$ . Prove that there exists a real number $C$ such that $a_{n} a_{n+1} < C$ for every positive integer $n$ .

Merlijn Staps

This post has been edited 5 times. Last edited by tapir1729, Jun 24, 2024, 9:35 PM

Z K Y

The post below has been deleted. Click to close.

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

1633 posts

#2 h Jun 24, 2024, 7:43 PM • 1 Y

Y by sami1618

If each term in this sequence is positive, the result follows.

Claim: $a_{2k} > a_{2k+2} \implies a_{2k+1} < a_{2k+3}$ and $a_{2k+1} < a_{2k+3} \implies a_{2k+2} > a_{2k+4}$ .
Proof. Follows by conditions. $\blacksquare$
As such, if $a_{2k} > a_{2k+2}$ or $a_{2k+1} < a_{2k+3}$ ever holds, then we get monotonicity where the evens always decrease and the odds always increase eventually. Truncate terms so this always hold.
Else, if this never holds, the evens always increase, and the odds always decrease.

Truncate the first term if necessary such that $a_1 > a_3 > a_5 > \dots$ and $a_2 < a_4 < a_6 < \dots$ .

Claim: WLOG we can assume that $a_1$ and $a_2$ are the same sign.
Proof. Note that $a_1a_2 < \max\{(a_1 - 10)(a_2 - N), (a_1 + N)(a_2 + N)\}$ holds for any $a_1, a_2$ and $N$ because $\frac{1}{2} ((a_1 - 10)(a_2 - 10) + (a_1 + 10)(a_2 + 10)) > a_1a_2.$ Then take $N > |a_1|, |a_2|$ . It suffices to show the sequences $a_1 + N, a_2 + N, \dots$ and $a_1 - N, a_2 - N, \dots$ are bounded.
Then WLOG flip the signs so they are positive. $\blacksquare$
Then if $a_{2k+1}$ is the first negative term, then $a_{2k+3}, a_{2k+5}, \dots$ are all negative. Since $a_{2n} > a_2$ , this gives us the fact that the sign eventually alternates, so the bound of $0$ suffices eventually.
Else, all $a_i$ are positive, so we finish by the bound $(a_1 + a_2)^2$ .

This post has been edited 2 times. Last edited by YaoAOPS, Jun 24, 2024, 7:44 PM

Z K Y

The post below has been deleted. Click to close.

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

779 posts

#3 h Jun 25, 2024, 2:13 AM • 1 Y

Y by sami1618

Define $\{c_i\}_{i\geq 2}$ by $c_{2n}=a_{2n+1}-a_{2n-1}$ for all $n\geq 1$ and $c_{2n+1}=a_{2n}-a_{2n+2}$ for all $n\geq 1.$ The condition implies that $\{c_i\}$ is strictly increasing.

$\textbf{Case 1: }$ $\{c_i\}$ is bounded
Let $\ell$ be the upper bound. Then we have
$\begin{align*} a_{2n+1}a_{2n+2} &= (a_1+c_2+c_4+\dots+c_{2n})(a_2-c_3-c_5-\dots-c_{2n+1})\\ &\leq\max((a_1+c_2+c_4+\dots+c_{2n})(a_2-c_4-c_6-\dots-c_{2n+2}),(a_1+c_2+c_4+\dots+c_{2n})(a_2-c_2-c_4-\dots-c_{2n})\\ &\leq\max\left((\tfrac{a_1+a_2+c_2-c_{2n+2}}{2})^2,(\tfrac{a_1+a_2}{2})^2\right)\\ &\leq \left(\frac{|a_1+a_2|+|\ell-c_2|}{2}\right)^2, \end{align*}$ $\begin{align*} a_{2n+1}a_{2n} &=(a_1+c_2+c_4+\dots+c_{2n})(a_2-c_3-c_5-\dots-c_{2n-1})\\ &\leq\max((a_1+c_2+c_4+\dots+c_{2n})(a_2-c_4-c_6-\dots-c_{2n}),(a_1+c_2+c_4+\dots+c_{2n})(a_2-c_2-c_4-\dots-c_{2n-2})\\ &\leq\max\left((\tfrac{a_1+a_2+c_2}{2})^2,(\tfrac{a_1+a_2+c_{2n}}{2})^2\right)\\ &\leq\left(\frac{|a_1+a_2|+|\ell|}{2}\right)^2, \end{align*}$ as needed.

$\textbf{Case 2: }$ $\{c_i\}$ is unbounded
For all $n$ sufficiently large, we have $a+c_2+c_4+\dots+c_{2n}>0$ and $a-c_3-c_5-\dots-c_{2n-1}<0.$ Therefore $a_{n}a_{n+1}<0$ for all sufficiently large $n,$ implying the conclusion.

This post has been edited 2 times. Last edited by amuthup, Jun 25, 2024, 2:14 AM

Z K Y

The post below has been deleted. Click to close.

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

406 posts

#4 h Jun 25, 2024, 10:01 AM

Y by

tapir1729 wrote:

An infinite sequence $a_1$ , $a_2$ , $a_3$ , $\ldots$ of real numbers satisfies
$a_{2n-1} + a_{2n} > a_{2n+1} + a_{2n+2} \qquad \mbox{and} \qquad a_{2n} + a_{2n+1} < a_{2n+2} + a_{2n+3}$ for every positive integer $n$ . Prove that there exists a real number $C$ such that $a_{n} a_{n+1} < C$ for every positive integer $n$ .

Merlijn Staps

$a_{2n-1} + a_{2n} > a_{2n+1} + a_{2n+2}$ (1)
$a_{2n+2}+a_{2n+3}>a_{2n}+a_{2n+1}$ (2)

Ading (1),(2) we get that : $a_{2n-1}+a_{2n+3}>2a_{2n+1}$ (3)
In (1) for $n\rightarrow n+1$ and adding (2) we get that $2a_{2n+2}>a_{2n+4}+a_{2n}$

Soppuse that there exist $i$ such that $a_{2i+1}<a_{2i+3}$ then for (3) we have that $a_{2j+1}$ is increasing from this point and then while from (1) we get that $a_{2j}$ is decresing.
Now for (4) we get that $a_{2n+2}-a_{2n}>a_{2n+4}-a_{2n+2}$ so at some point we get that $a_{2k}<0$ and so $a_ia_{i+1}<0$ and is decresing.

Soppuse now that there is no such $i$ exist then $a_{2i+1}$ is decresing and from (2) we get that $a_2i$ is incresing.
If there exist $e$ such that $a_{2n+1}-a_{2n+3}>e$ for every $n$ then there exist $k$ such that $a_{2k+1}<0$ and we are done.
If no such $e$ exist then we have that $\lim_{n\rightarrow +\infty }a_{2n+1}-a_{2n+3}=0$ and from (1) we get that:
$\lim_{n\rightarrow +\infty }(a_{2n+1}-a_{2n+3})=0\geqslant \lim_{n\rightarrow +\infty }(a_{2n+2}-a_{2n})\geqslant 0\Rightarrow \lim_{n\rightarrow +\infty }(a_{2n+2}-a_{2n})=0$
So for $n>N$ we get that $a_{2n+1}$ belongs $[x,x+a]$ and $a_{2n}$ belongs to $[y,y+b]$ so we are done.

Z K Y

The post below has been deleted. Click to close.

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

973 posts

#5 h Jun 25, 2024, 12:43 PM • 1 Y

Y by GeoKing

Let $d_n=a_n-a_{n-2}$ . The conditions become $0>d_{2n+1}+d_{2n+2} \;\;\; \text{and} \;\;\; 0<d_{2n+2}+2_{2n+3}$ Adding shifted versions of these yields that the odd $d_i$ are strictly increasing and even $d_i$ are strictly decreasing. Thus there must exist a point where the even $d_i$ and the odd $d_i$ stay the same sign. Notice that $a_{2k}=a_2+d_4+d_6+\dots+d_{2k}$ and $a_{2k+1}=a_1+d_3+d_5+\dots+d_{2k+1}$ . Thus there must exist a point where the even $a_i$ and the odd $a_i$ stay the same sign (it doesn't hurt to assume this happens right away). If they are different in sign, then were clearly done. If they are both positive then the first inequality implies that $a_i<a_1+a_2$ so we can easily chose a $C$ . If they are both negative then the second inequality implies that $a_i>a_2+a_3$ so we can easily chose a $C$ .

Z K Y

The post below has been deleted. Click to close.

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

3398 posts

#6 h Jun 29, 2024, 11:17 PM

Y by

Claim: Eventually the odd indices are increasing while the even indices are decreasing, or the other way around.
Proof. By the given conditions we have $a_{2n+1} - a_{2n-1} < a_{2n} - a_{2n+2} < a_{2n+3} - a_{2n+1}$ , so if $a_{2n+1} > a_{2n-1}$ once, then the odds will increase will evens will decrease from then on. If this never happens, then the odds will decrease while evens will increase.

Now, we do a casework bash to finish the problem.

Case 1. $a_1, a_2 > 0$ or $a_1, a_2 < 0$

Note that in the first subcase, the first condition implies $a_i < a_1+a_2$ for all i, meaning we can take $C = (a_1+a_2)^2$ , because the sequences cannot both become negative. Similarly, for the second subcase, the second condition implies $a_i > a_2 + a_3$ for all $i$ , implying that $C = (a_2+a_3)^2$ works, because the sequences cannot both become positive.

Case 2. $a_1, a_2$ are opposite signs

If the two sequences keep their initial signs or they both end up swapping their signs, then selecting $C$ is trivial because $a_ia_{i+1} < 0$ for large $i$ . If two sequences end up being the same sign after some time, then we can finish by the first case.

This post has been edited 3 times. Last edited by pi271828, Jun 29, 2024, 11:19 PM

Z K Y

The post below has been deleted. Click to close.

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

76 posts

jp62

#7 h Jun 30, 2024, 2:31 PM

Y by

Consider the sequence $\{b_i\}_{i=1}^\infty$ defined by $b_i=(-1)^ia_i$ . Let $d_i=b_{i+2}-b_i$ .
The conditions simplify to $d_i>d_{i+1}$ for all positive integers $i$ , and we want to show that $b_nb_{n+1}$ is bounded below since we flipped the sign of exactly one of $a_n$ and $a_{n+1}$ .
It suffices to prove that the product is bounded for all sufficiently large $n>N$ as we can take the minimum of that bound and $b_nb_{n+1}$ for $n\leq N$ .

If $d$ is eventually nonpositive, say $d_k$ is the first $d$ that is $\leq0$ , then all $d_i$ are at most $d_{k+1}<0$ . This means that the $b$ sequence is bounded above by a strictly decreasing linear function, and thus is eventually always negative. So $b_nb_{n+1}>0$ for all sufficiently large $n$ .

Otherwise, $d$ is always positive, which means the $b$ sequence is increasing. If $b$ is bounded, the final condition is clearly true. Otherwise, at least one of the partial sums $d_1+d_3+\dots+d_{2k-1}$ and $d_2+d_4+\dots+d_{2k}$ is unbounded in the positive direction, but the $d_i$ decreasing condition implies that both must be unbounded (the partial sums can be bounded by each other up to some constant). This means that $b$ is eventually positive, so $b_nb_{n+1}$ is eventually positive for sufficiently large $n$ .

Z K Y

The post below has been deleted. Click to close.

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

180 posts

dkedu

#8 h Jun 30, 2024, 9:45 PM

Y by

Write the condition as $a_1 + a_2 > a_3+a_4 > \cdots$ and $a_2 + a_3 < a_4 + a_5 < \cdots$ .

If $a_{2k-1} < a_{2k+ 1}$ or $a_{2k-2} > a_{2k}$ , then we have $a_{2k-1} < a_{2k+1} < \cdots$ and $a_{2k-2} > a_{2k} > \cdots$ . If this happens, we just remove terms so that $a_1 < a_3 < \cdots$ and $a_2 > a_4 > \cdots$ . If $a_1, a_2$ are the same signs, $|a_i - a_{i+2}|$ is increasing and nonzero, so we get that eventually for some $N$ , we have $a_{2k+1} > 0$ , $a_{2k} < 0$ for $k > N$ . This means that there are only finite many $a_i a_{i+1} > 0$ , so it is bounded.

So we assume that $a_1 > a_3 > \cdots$ and $a_2 < a_4 < \cdots$ . Note that if they have different signs, then we have that $a_ia_{i+1} < 0$ . $a_i, a_{i+1}$ must share a sign at some $N$ otherwise we take $C = 0$ . However, if $a_N, a_{N+1}$ are the first consecutive terms to share a sign, we just take bound $(a_N + a_{N+1})^2$ to finish.

Z K Y

The post below has been deleted. Click to close.

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

141 posts

Ywgh1

#9 h Sep 2, 2024, 7:53 PM

Y by

By adding the two conditions we can see that
$a_1<a_3<a_5 \dots \qquad \mbox{and} \qquad a_2>a_4>a_6 >\dots$
Let's focus on $a_1$ and $a_2$ .

Case 1: Both are positive or both are negative.

If we have that both are positive, We have that $a_1+a_2 > a_3+a_4 > a_5+a_6 \dots$ by spamming the first condition of the problem. So we get that $a_i<a_2+a_1$ .

Hence setting $C=(a_1+a_2)^2$ is sufficient.
Similarly for both being negative we can set $C=(a_2+a_3)^2$ .

Case 2: They have opposite signs.

Then we have that $a_na_{n+1}<0$ , now if for sufficiently large $n$ they get same sign, then that’s dealt with in case one, hence we are done!

This post has been edited 1 time. Last edited by Ywgh1, Sep 2, 2024, 7:53 PM

Z K Y

The post below has been deleted. Click to close.

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

295 posts

#10 h Jan 10, 2025, 8:33 PM

Y by

solved with lelouchvigeo

solution

This post has been edited 2 times. Last edited by InterLoop, Jan 10, 2025, 8:34 PM

Z K Y

The post below has been deleted. Click to close.

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

777 posts

#11 h May 22, 2025, 4:00 PM

Y by

Screw this problem I wasted 2+ hours investigating a very promising solution pathway that led nowhere.

Quote:

$b_1 = a_1, b_2 = a_2, b_3 = a_3, b_n = b_{n-3} + b_{n-2} - b_{n-1}$ and compare $b_i$ with $a_i$ . Using generating functions,
$b_n = (an + b) (-1)^n + c$ For an increasing sequence $d_i$ of positive reals,
$\Longrightarrow a_n = (an + b + d_i) (-1)^n + c$

I should not have used DFS problem solving without a recursion limit and I should have looked at the other problems sooner :C

Z K Y

The post below has been deleted. Click to close.

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

8904 posts

#12 h May 22, 2025, 6:32 PM

Y by

A bit verbose and badly written solution, but whatever.

We need the following claim:

Claim: For each positive integer $n$ , $a_{2n-1} + a_{2n+3} > 2a_{2n+1}$ , and $a_{2n} + a_{2n+4} < 2a_{2n+2}$ .

Proof: For the first inequality, $2a_{2n+1} + a_{2n+2} - a_{2n-1} < a_{2n} + a_{2n+1} < a_{2n+2} + a_{2n+3}.$ For the second inequality, $2a_{2n+2} + a_{2n+3} - a_{2n} > a_{2n+1} + a_{2n+2} > a_{2n+3} + a_{2n+4}.$ This proves the claim. $\blacksquare$

So now consider the subsequences $\{b_n\} = \{a_{2n-1}\}$ and $\{c_n\} = \{a_{2n}\}$ . Suppose for the sake of contradiction that the result is not true; then there exists an $n$ such that $b_n$ and $c_n$ are the same sign; without loss of generality, suppose they are both positive.

Claim: Let $d = c_n - c_{n+1}$ . Then for each positive integer $k$ , $c_{n+k} < c_n - kd$ .

Proof: Clear by induction and the inequality $c_{n-1} + c_{n+1} < 2c_n$ from before. $\blacksquare$

Indeed, the reverse inequality holds for $d = b_{n+1} - b_n$ and the $b_i$ . Thus, if there exists an index $N$ such that $c_{N+1} < c_N$ , it follows that $b_{N+2} > b_{N+1}$ as $c_N + b_{N+1} < c_{N+1} + b_{N+2}$ , and the above two claims show that $c_n$ is eventually negative and $b_n$ eventually positive, which means the product is bounded from above.

So now suppose that this is not true, i.e. $c_N \leq c_{N+1}$ for all $N \geq n$ ; this implies that $c_n$ is positive for all $n \geq N$ . Furthermore, the given inequalities show that $b_N > b_{N+1}$ for every $N \geq n$ . Now note that the sum $b_N + c_N$ is bounded above by $b_n + c_n$ , hence $b_N c_N \leq \tfrac 14(b_N+c_N)^2 \leq \tfrac 14(b_n+c_n)^2$ . For the product $b_{N+1}c_N$ , note that:

If $b_N$ is negative, then $b_{N+1} < b_N < 0$ and $c_Nb_{N+1} < 0$ as $c_N$ is positive;
If $b_N$ is positive, then $c_N < c_N+b_N < c_n+b_n$ and $b_{N+1} < b_n+c_n-c_{N+1} < b_n+c_n$ , hence $b_{N+1} c_N < (c_n+b_n)^2$ is constant.

This concludes the proof.

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

737 posts

cursed_tangent1434

#13 h Jul 3, 2025, 3:59 AM

Y by

We refer to the sequence $a_2,a_4,\dots$ as the even sequence and the sequence $a_1,a_3,\dots$ as the odd sequence. The sequence satisfies the following important property.

Claim : Eventually either the even sequence or odd sequence is strictly increasing while the other is strictly decreasing.

Proof : If there exists some positive integer $n$ for which $a_{2n+1}>a_{2n+3}$ note,
$a_{2n-1}+a_{2n}>a_{2n+1}+a_{2n+2}>a_{2n+2}+a_{2n+3}>a_{2n}+a_{2n+1}$ which implies that $a_{2n-1}>a_{2n+1}$ and a straightforward induction then yields, $a_1 > a_3>\dots > a_{2n+3}$ . So, if the odd sequence ever increases it cannot decrease again.

Similarly, if there exists some positive integer $n$ such that $a_{2n}<a_{2n+2}$ note,
$a_{2n-1}+a_{2n}> a_{2n+1}+a_{2n+2}>a_{2n}+a_{2n+1}> a_{2n-2}+a_{2n-1}$ so $a_{2n}>a_{2n-2}$ and a straightforward induction yeilds, $a_2<a_4<\dots < a_{2n+2}$ . So, if the even sequence ever decreases it cannot increase again.

Thus, the odd sequence is strictly decreasing in which case the even sequence must be eventually strictly increasing (in order to not contradict the second inequality) or it is eventually strictly increasing in which case the even sequence must be strictly decreasing (in order to not contradict the first inequality) which is precisely what we claimed.

Now, if the decreasing sequence even decreases below zero, the result is clear as $a_na_{n+1}<0$ for all sufficiently large $n$ and hence is upper bounded. Hence, assume that the decreasing sequence is bounded below by a positive real constant $R$ . WLOG consider the even sequence to be decreasing since the other case is entirely symmetric.

Claim : If the even sequence is eventually strictly decreasing but bounded below by $R$ , the odd sequence is bounded above by some real constant $T$ .

Proof : Simply note that for all positive integers $n$ , the first inequality rearranges to
$a_{2n+1}-a_{2n-1}<a_{2n}-a_{2n+2}$ Hence, the increments of the odd sequence in each step are strictly less than the decrements of the even sequence. Since the even sequence is bounded below it immediately follows that the odd sequence is also bounded above.

Thus, it is clear that the product $a_{n}a_{n+1}$ has an upper bound since the increasing sequence does not grow arbitrarily large, and we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a