Mount Inequality erupts on a sequence :o

The post below has been deleted. Click to close.

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

815 posts

#1 h Jul 9, 2023, 4:43 AM • 23 Y

Y by EthanWYX2009, Amir Hossein, OronSH, mathfan2020, GeoKing, Supercali, Mogmog8, mathmax12, dangerousliri, oolite, Schur-Schwartz, centslordm, ismayilzadei1387, ihatemath123, Lamboreghini, Sedro, buddyram, aidan0626, megarnie, seifbaba, A21, cubres, farhad.fritl

Let $x_1,x_2,\dots,x_{2023}$ be pairwise different positive real numbers such that
$a_n=\sqrt{(x_1+x_2+\dots+x_n)\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)}$ is an integer for every $n=1,2,\dots,2023.$ Prove that $a_{2023} \geqslant 3034.$

This post has been edited 6 times. Last edited by GrantStar, Jul 9, 2023, 4:54 AM
Reason: Renaming source

Z K Y

The post below has been deleted. Click to close.

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

beansenthusiast505

26 posts

beansenthusiast505

#2 h Jul 9, 2023, 4:44 AM • 1 Y

Y by cubres

inequality has returned, my prayers were not answered (i’m not in imo and prob trying later but it should be p1/4 difficulty)

This post has been edited 1 time. Last edited by beansenthusiast505, Jul 9, 2023, 4:45 AM

Z K Y

The post below has been deleted. Click to close.

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

qwedsazxc

167 posts

qwedsazxc

#3 h Jul 9, 2023, 4:47 AM • 13 Y

Y by mathleticguyyy, adorefunctionalequation, Hyperabola, Geometry285, GeoKing, Rebel_1, rightways, Celestialer, centslordm, Lamboreghini, aidan0626, Lichenw, cubres

Let's show that $a_{n+2}\geq a_n+3$ for all $n$ . By C-S and AM-GM:
$a_{n+2}\geq a_n+\sqrt{\frac{(x_{n+1}+x_{n+2})^2}{x_{n+1}x_{n+2}}}>a_n+2.$ Therefore $a_{n+2}\geq a_n+3$ . Since $a_1=1$ , $a_{2023}\geq a_{2021}+3\geq\cdots\geq a_1+3033=3034$ .

Z K Y

The post below has been deleted. Click to close.

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

EthanWYX2009

842 posts

EthanWYX2009

#4 h Jul 9, 2023, 4:49 AM • 7 Y

Y by GeoKing, ike.chen, ys-lg, Euler_Gauss, ehuseyinyigit, Lamboreghini, DrPoe1898

Motivation. It is obvious to see that $3034=2022\times\frac 32+1,$ which leads us to the lemma below $.$
Lemma. For $\forall n\in\mathbb Z_+,a_{n+2}\geq a_n+3.$
Lemma Proof. As $a_n,a_{n+2}\in\mathbb Z_+,$ we only need to prove that $a_{n+2}>a_n+2.$ Using Cauchy inequality $,$
$\begin{aligned}a_{n+2}=\sqrt{\sum\limits_{k=1}^{n+2}x_k\sum\limits_{k=1}^{n+2}\frac 1{x_k}}&\geqslant\sqrt{\sum\limits_{k=1}^{n}x_k\sum\limits_{k=1}^{n}\frac 1{x_k}}+\sqrt{(x_{n+1}+x_{n+2})\left(\frac 1{x_{n+1}}+\frac 1{x_{n+2}}\right)}\\&=a_n+\sqrt{4+\frac{(x_{n+1}-x_{n+2})^2}{x_{n+1}x_{n+2}}}>a_n+2.\blacksquare\\\end{aligned}$ Proof. Using Lemma we have $a_{2023}\geq a_{2021}+3\geq\cdots\geq a_1+3\times 1011=3034.\blacksquare$

This post has been edited 2 times. Last edited by EthanWYX2009, Jul 9, 2023, 1:30 PM

Z K Y

The post below has been deleted. Click to close.

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

juckter

322 posts

juckter

#5 h Jul 9, 2023, 5:04 AM • 2 Y

Y by Johnson100, Saniva_Rakib_Soha

We claim $a_{n + 2} \ge a_n + 3$ which is clearly enough. Let $s_n = x_1 + x_2 + \dots + x_n$ and $h_n = \frac{1}{x_1} + \frac{1}{x_2} + \dots + \frac{1}{x_n}$ . Then

$a_{n + 1}^2 = s_{n + 1}h_{n + 1} = (s_n + x_{n + 1})\left(h_n + \frac{1}{x_{n + 1}}\right) = s_nh_n + \left(\frac{s_n}{x_{n + 1}} + x_nh_{n + 1}\right) + 1 = a_n^2 + \left(\frac{s_n}{x_{n + 1}} + x_{n + 1}h_n\right) + 1$
By AM-GM we have $\frac{s_n}{x_{n+1}} + x_{n+1}h_n \ge 2\sqrt{s_nh_n} = 2a_1$ and therefore $a_{n + 1}^2 \ge a_n^2 + 2a_n + 1 = (a_n + 1)^2$ . Thus $a_{n + 1} \ge a_n + 1$ for all $n$ , with equality if and only if $\frac{s_n}{x_{n+1}} = x_{n+1}h_n$ , or $x_{n+1}^2 = \frac{s_n}{h_n}$ . We finally prove that equality cannot happen twice in a row. Otherwise we have

$x_{n + 1}^2 = \frac{s_{n + 1}}{h_{n + 1}} = \frac{s_n + x_{n + 1}}{h_n + \frac{1}{x_{n + 1}}} = \frac{s_n + \sqrt{\frac{s_n}{h_n}}}{h_n + \sqrt{\frac{h_n}{s_n}}} = \frac{s_n}{h_n} = x_n^2$
A contradiction as $x_1, x_2, \dots, x_{2023}$ are all distinct.

Z K Y

The post below has been deleted. Click to close.

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

S.Ragnork1729

214 posts

S.Ragnork1729

#6 h Jul 9, 2023, 5:41 AM • 1 Y

Y by Johnson100

Solution : We will move on with a claim first.
Claim : $a_{n+2} > a_n+2$
Proof : Observe that $a_{n+2} > a_n+2$ $\Longleftrightarrow \sqrt{(x_1+....+x_{n+2})(\frac{1}{x_1}+....+\frac{1}{x_{n+2}}} > \sqrt{(x_1+....+x_{n})(\frac{1}{x_1}+....+\frac{1}{x_{n}}} +2 .$ Now let $y=\sum_{i=1}^{n} x_i$ and $z=\sum_{i=1}^{n} \frac{1}{x_i}$ , then we have to show $\sqrt{(y+x_{n+1}+x_{n+2})(z+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} > \sqrt{yz}+2$ $\Longleftrightarrow yz+y(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})+z(x_{n+1}+x_{n+2})+(x_{n+1}+x_{n+2})(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}) > yz+4\sqrt{yz}+4$ and it is obvious by AM-GM.
Hence we get $a_{2023} \geq a_{2021}+3 \geq a_{2019}+6 \geq \cdots a_4+3030 \geq a_1+3033 =1+3033=3034 .$ Note : The problem was very good but the main part was to prove $a_{n+2} \geq a_{n}+3$ using AM-GM and Algebraic Expansion.

This post has been edited 2 times. Last edited by S.Ragnork1729, Jul 9, 2023, 6:08 AM

Z K Y

The post below has been deleted. Click to close.

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

mathuz

1512 posts

mathuz

#7 h Jul 9, 2023, 5:53 AM

Y by

Obviously, $a_n$ should be an increasing (strictly) sequence of positive integers with $a_1=1$ . We will show that $a_{n+1}=a_n+1$ and $a_{n+2} = a_{n+1}+1$ doesn't hold at the same time. Assume it does.

We know that $a_{n+1}^2-a_n^2=x_{n+1}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n}}\right) + \frac{1}{x_{n+1}} \left(x_1+\ldots +x_n\right)+1 = 2a_n+1$ and $2a_n = x_{n+1}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n}}\right) + \frac{1}{x_{n+1}} \left(x_1+\ldots +x_n\right) \ge 2a_n$ by AM-GM, so we should have $x_{n+1}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n}}\right) = \frac{1}{x_{n+1}} \left(x_1+\ldots +x_n\right) = a_n.$ Similarly, we can obtain $x_{n+2}\left(\frac{1}{x_1}+\ldots +\frac{1}{x_{n+1}}\right) = \frac{1}{x_{n+2}} \left(x_1+\ldots +x_{n+1}\right) = a_{n+1}.$ That means $a_nx_{n+1}+x_{n+1}=x_1+x_2+\ldots +x_n+x_{n+1} = a_{n+1}x_{n+2}$ and since $a_{n+1}=a_n+1$ we get that $x_{n+1}=x_{n+2}$ , which is a contradiction.

Hence, if $a_{n+1}-a_n=1$ then $a_{n+2}-a_{n+1}>1$ , or vice versa. In any case, $a_{n+2}-a_n\ge 3$ and $a_{2023} \ge a_1+3\cdot 1011 = 3034$ .

Z K Y

The post below has been deleted. Click to close.

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

GrantStar

815 posts

GrantStar

#8 h Jul 9, 2023, 6:05 AM • 8 Y

Y by RobertRogo, GeoKing, centslordm, ehuseyinyigit, Lamboreghini, channing421, aidan0626, Jack_w

Solution without words

Reason that doing the same thing for gaps of one fails

This post has been edited 2 times. Last edited by GrantStar, Jul 9, 2023, 6:12 AM

Z K Y

The post below has been deleted. Click to close.

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

Alfredfeed

9 posts

Alfredfeed

#9 h Jul 9, 2023, 6:24 AM

Y by

Solution without using AM-GM
Lets prove $a_{n+1}$ $\geq$ $a_{n-1}+3$

s = $x_1 + x_2 + ... + x_{n-1}$

h = $\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_{n-1}}$

$a^2_{n-1}$ = hs

$a^2_{n} = (s+x_n)(h+\frac{1}{x_n})$

$a^2_{n} = hs + \frac{s}{x_n} + {x_n}h + 1$

$a^2_{n-1} = a_{n-1}^2 + \frac{s}{x_n} + xh + 1$

assume $a^2_{n}$ = $a_{n-1}+1$ ; $a^2_{n+1}$ = $a_{n}+1$

otherwise its trivial since obviously $a_{n-1}<a_{n}$

2 $a_{n-1}=\frac{s}{x_n}+xh$

$h=\frac{a^2}{s}$

2 $a_{n-1}=\frac{s}x+\frac{x}s{a_{n-1}^2}$

let $k = \frac{s}x$

2 $a_{n-1}$ =k+ $\frac{1}k{a_{n-1}^2}$

solving for $a_{n-1}$ , we get:

$a_{n-1}$ = $\frac{s}x$

s= $a_{n-1}$ x

$a_{n-1}+1=\frac{s+x}x'$

x'(a+1)=x(a+1)

x'=x
contradiction, so $a_{n+1}$ $\geq$ $a_{n-1}+3$

Z K Y

The post below has been deleted. Click to close.

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

AnonymousBunny

339 posts

AnonymousBunny

#10 h Jul 9, 2023, 6:29 AM • 1 Y

Y by GeoKing

The crucial claim is the following:

Claim: For any $n$ , it cannot be the case that $a_{n+1} = a_n + 1$ and $a_{n+2} = a_{n+1}+1$ .
Proof:
Suppose, FTSOC, $a_{n+1} = a_n + 1, a_{n+2} = a_{n+1}+1$ .

$a_{n+1} = a_n + 1 \iff x_{n+1} \left( x_1 + x_2 + \cdots + x_n \right) + \dfrac{1}{x_{n+1}} \left(x_1 + \cdots + x_n \right) = 2a_n$

Treat this as a quadratic in $x_{n+1}$ : its discriminant vanishes and the only root is $x_{n+1} = \dfrac{a_n}{1/x_1 + \cdots + 1/x_n}$ .
Similarly, $x_{n+2} = \dfrac{a_{n}+1}{1/x_1 + \cdots + 1/x_{n+1}}$ . I now claim that $x_{n+1} = x_{n+2}$ , which is a contradiction. This follows from a simple calculation:

$x_{n+1} = x_{n+2} \iff a_n \left( \dfrac{1}{x_1} + \cdots + \dfrac{1}{x_{n+1}}\right) = (a_n+1) \left( \dfrac{1}{x_1} + \cdots + \dfrac{1}{x_n} \right) \iff x_{n+1} = \dfrac{a_n}{1/x_1+\cdots + 1/x_n} \blacksquare$
Now, note that $a_2 \geq 2$ by Cauchy-Schwartz. Since equality cannot hold (as $x_1, x_2$ are distinct), in fact, $a_2 \geq 3$ . Also note that $a_n$ is strictly increasing. The claim shows that $a_i$ must jump more than one once every two steps, i.e., $a_{n+2} \geq a_n + 3$ . Applying this inequality repeatedly gives the result.

Z K Y

The post below has been deleted. Click to close.

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

Manteca

52 posts

Manteca

#11 h Jul 9, 2023, 6:35 AM • 2 Y

Y by ZNatox, GeoKing

$a_{n+1}^2 = a_n^2 + 1 + x_{n+1}(\frac{1}{x_1}+ \cdots + \frac{1}{x_{n}}) + \frac{1}{x_{n+1}}(x_1 + \cdots + x_{n}) \geq a_n^2 + 1 + 2a_n = (a_n+1)^2$ By AM-GM, with equality if and only if the two things we are summing are equal, in particular $x_{n+1} = \sqrt{\frac{A}{B}}$ where $A = \sum a_i$ and $B = \sum \frac{1}{a_i}$ .
If also $a_{n+2} = a_{n+1} + 1$ then again we must have $x_{n+2} = \sqrt{\frac{A+\sqrt{\frac{A}{B}}}{B+\sqrt{\frac{B}{A}}}}$ but both things inside the square root are equal so $x_{n+1} = x_{n+2}$ but that cant happen so at least $a_{n+2} \geq a_n + 3$ . Finally $a_{2023} \geq 1 + 3 \cdot 1011 = 3034$ as we wanted to show.

This post has been edited 1 time. Last edited by Manteca, Jul 9, 2023, 6:37 AM

Z K Y

The post below has been deleted. Click to close.

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

djmathman

7936 posts

djmathman

#12 h Jul 9, 2023, 6:44 AM • 2 Y

Y by Assassino9931, RobertRogo

Sneaky little bugger.

Define $A_n := x_1 + x_2 + \cdots + x_n$ and $B_n := \tfrac 1{x_1} + \tfrac1{x_2} + \cdots + \tfrac1{x_n}$ . Observe that
$\begin{align*} a_{n+1}^2 &= \left(A_n + x_{n+1}\right)\left(B_n + \frac{1}{x_{n+1}}\right) \\ &= A_nB_n + \frac{A_n}{x_{n+1}} + B_n x_{n+1} + 1 \\ &\geq A_nB_n + 2\sqrt{A_nB_n} + 1 = (a_n + 1)^2. \end{align*}$ Hence $a_{n+1} \geq a_n + 1$ .

We now prove the stronger inequality $a_{n+2} \geq a_n + 3$ . Suppose, by way of contradiction, that $a_{n+2} = a_n + 2$ . Then equality cases in both inequalities above (i.e. for $a_{n+1}$ and $a_{n+2}$ ) hold, so $x_{n+1} = \sqrt{\tfrac{A_n}{B_n}}$ and
$x_{n+2}^2 =\frac{A_n + x_{n+1}}{B_n + \frac 1{x_{n+1}}} = \frac{A_n + \sqrt{\frac{A_n}{B_n}}}{B_n + \sqrt{\frac{B_n}{A_n}}}= \frac{A_n}{B_n}.$ (The last equality is true because $\tfrac{x_{n+1}}{\frac{1}{x_{n+1}}} = x_{n+1}^2 = \tfrac{A_n}{B_n}$ .) This contradicts the fact that the $x_j$ are pairwise distinct.

Remark. I think the claims here are motivated, but the main sticking point for me was getting over my confusion about why the bound wasn't tighter. (It didn't help that I made a few algebra mistakes along the way.) Proving the inequality $a_{n+2} \geq a_n + 3$ directly is certainly faster, but this solution shows why we need to consider this stronger bound in the first place.

Z K Y

The post below has been deleted. Click to close.

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

Minkowsi47

48 posts

Minkowsi47

#13 h Jul 9, 2023, 7:34 AM

Y by

MOTIVATION : The thing which motivate $a_{n+2} \geq a_{n}+3$ is $a_{2023}\geq 3034$ as actually this is the point for me which makes me realise to follow up this claim. proving that claim is same as GrantStar did and finishes up the problem. :-D

This post has been edited 1 time. Last edited by Minkowsi47, Jul 9, 2023, 7:35 AM

Z K Y

The post below has been deleted. Click to close.

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

Tintarn

9031 posts

Tintarn

#14 h Jul 9, 2023, 7:37 AM • 2 Y

Y by carefully, ehuseyinyigit

So. Is the bound $3034$ actually sharp?

Z K Y

The post below has been deleted. Click to close.

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

PythZhou

6 posts

PythZhou

#15 h Jul 9, 2023, 7:39 AM

Y by

Too easy for IMO inequality.
Claim : $a_{n+2}>a_{n}+2$ which is equivalent to $a_{n+2} \ge a_{n}+3$ since $a_n$ is an integer. Hence $a_{2023} \ge a_1+\sum_{n=1}^{1011}3=3034$
Then prove the claim:

We define $X_n=x_1 + x_2 + \cdots + x_n$ and $Y_n=\frac{1}{x_1}+\cdots+\frac{1}{x_{n}}$ , so $a_n=\sqrt{X_n Y_n}$
$\begin{align*} a_{n+2}=&\sqrt{(x_1 + x_2 + \cdots + x_n+x_{n+1}+x_{n+2}) (\frac{1}{x_1}+\cdots+\frac{1}{x_{n}}+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} \\ &= \sqrt{(X_n+x_{n+1}+x_{n+2})(Y_n+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} \\ &= \sqrt{a_n^2+X_n(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})+Y_n(x_{n+1}+x_{n+2})+(x_{n+1}+x_{n+2})(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})} \\ &> \sqrt{a_n^2+ 4 \sqrt{X_nY_n}+4} \\ &= \sqrt{a_n^2+4a_n+4}=a_n+2 \end{align*}$

Z K Y

The post below has been deleted. Click to close.

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

blueberryfaygo_55

339 posts

blueberryfaygo_55

#79 h Jun 15, 2024, 11:43 PM • 1 Y

Y by KevinYang2.71

Claim 1. $a_2 \geq 3$ .
Proof. We have $\begin{align*} a_2 &= \sqrt{(x_1+x_2) \left(\dfrac{1}{x_1} + \dfrac{1}{x_2}\right)} \\ &= \sqrt{2 + \dfrac{x_1}{x_2} + \dfrac{x_2}{x_1}} \end{align*}$ By AM-GM, $\dfrac{x_1}{x_2} + \dfrac{x_2}{x_1} > 2$ , and the equality case doesn't occur as $x_1 \neq x_2$ . Thus, $\begin{align*} a_2 &> \sqrt{2+2} \\ &= 2 \end{align*}$ but $a_2$ is an integer, so we must have $a_2 \geq 3$ . $\blacksquare$

Claim 2. $a_n \geq \dfrac{3n-1}{2}$ for all positive odd $n$ up to $2023$ , which directly implies the result.
Proof. We use induction. The base case is trivial since $a_1 = 1$ for any $x_1$ . Now, suppose that $a_k = \sqrt{(x_1+x_2+\cdots+x_k) \left(\dfrac{1}{x_1} + \dfrac{1}{x_2} + \cdots + \dfrac{1}{x_k}\right)} \geq \dfrac{3k-1}{2}$ or $a_k^2 \geq \dfrac{(3k-1)^2}{4}$ for positive integer $k$ . We have $\begin{align*} a_{k+2} &= \sqrt{(x_1+x_2+\cdots+x_k + x_{k+1} + x_{k+2}) \left(\dfrac{1}{x_1} + \dfrac{1}{x_2} + \cdots + \dfrac{1}{x_k} + \dfrac{1}{x_{k+1}} + \dfrac{1}{x_{k+2}} \right)} \\ &= \sqrt{(x_1+\cdots+x_k) \left(\dfrac{1}{x_1} + \cdots + \dfrac{1}{x_k} \right) + (x_1 + \cdots + x_k) \left(\dfrac{1}{x_{k+1}} + \dfrac{1}{x_{k+2}} \right) + (x_{k+1}+x_{k+2})\left(\dfrac{1}{x_{k+1}} + \dfrac{1}{x_{k+2}}\right)} \\ &\geq \sqrt{\dfrac{(3k-1)^2}{4} + (x_1 + \cdots + x_k) \left(\dfrac{1}{x_{k+1}} + \dfrac{1}{x_{k+2}}\right) + \dfrac{(x_{k+1}+x_{k+2})(3k-1)^2}{4(x_1+\cdots+x_k)} + 9} \, \, \text{(by the inductive hypothesis and Claim 1)} \\ &\geq \sqrt{\dfrac{(3k-1)^2}{4} + 3(3k-1)+9} \, \, \text{(by Claim 1 and AM-GM)} \\ &= \sqrt{\left(\dfrac{(3k-1)}{2} + 3 \right)^2} \\ &= \dfrac{3k-1}{2} + 3 \\ &= \dfrac{3(k+2)-1}{2} \end{align*}$ which completes the induction proof. $\blacksquare$
We may finally note that equality holds when $(x_{k+1}+x_{k+2}) \left(\dfrac{1}{x_{k+1}} + \dfrac{1}{x_{k+2}}\right) = 9$ , or $x_{k+2} = \dfrac{(7-\sqrt{45})}{2} \cdot x_{k+1}$ , and $(x_1 + \cdots + x_k) \left(\dfrac{1}{x_{k+1}} + \dfrac{1}{x_{k+2}} \right) = \dfrac{(x_{k+1}+x_{k+2})(3k-1)^2}{4(x_1+\cdots+x_k)} + 9$ which is ultimately equivalent to any $x_1, \cdots, x_k$ satisfying $x_1 + \cdots + x_k = \dfrac{(3k-1)\sqrt{(x_{k+1})(x_{k+2})}}{2}.$

Z K Y

The post below has been deleted. Click to close.

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

PEKKA

1838 posts

PEKKA

#83 h Jun 26, 2024, 9:08 PM

Y by

For brevity, let $A_k=\sum_{i=1}^{k}x_i, ~~ \text{and} B_k=\sum_{i=1}^{k}\frac{1}{x_i}.$ We will show using induction that $a_n \ge \frac{3n-1}{2}.$
Proof:
Base Case: $a_1=\sqrt{x_1\frac{1}{x_1}}=1\ge \frac{3(1)-1}{2}.$
Inductive hypothesis: Assume $a_m \ge \frac{3m-1}{2}$ for $1 \le m\le k.$
Then $a_{k+1}=\sqrt{\left(A_k+x_{k+1}\right)\left(B_k+\frac{1}{x_{k+1}}\right)}=\sqrt{A_kB_k+1+\frac{A_k}{x_{k+1}}+B_kx_{k+1}}\ge \sqrt{\left(\frac{3k-1}{2}\right)^2+1+\frac{A_k}{x_{k+1}}+B_kx_{k+1}}.$ Let's examine the terms with $x_k+1$ in them.
$\frac{A_k}{x_{k+1}}+B_kx_{k+1}=\sum_{i=1}^k \left(\frac{x_{k+1}}{x_i}+\frac{x_i}{x_{k+1}}\right).$ Claim: For all $1\le i \le n,$ $\left(\frac{x_{k+1}}{x_i}+\frac{x_i}{x_{k+1}}\right) \ge 7.$
Proof: By the 2-variable case of our inductive hypothesis(strong induction), $a_2 \ge \frac{5}{2}.$ Since $a_2$ is an integer by the problem statement, $a_2 \ge 3.$ Therefore, for pairwise different $x_a,x_b,$ $\sqrt{(x_a+x_b) \left(\frac{1}{x_a}+\frac{1}{x_b}\right)}\ge 3.$ Squaring both sides and subtracting 2, we show that our claim is true.

Therefore, going back to our induction,
$\frac{A_k}{x_{k+1}}+B_kx_{k+1}=\sum_{i=1}^k \left(\frac{x_{k+1}}{x_i}+\frac{x_i}{x_{k+1}}\right)\ge 7k.$ Plugging this back into the expression for $a_{k+1},$ we get
$a_{k+1} \ge \sqrt{\left(\frac{3k-1}{2}\right)^2+1+\frac{A_k}{x_{k+1}}+B_kx_{k+1}}\ge \sqrt{\left(\frac{3k-1}{2}\right)^2+1+7n}=\sqrt{\frac{9k^2-6k+1}{4}+7k+1}=\sqrt{\frac{9k^2-6k+1+28k+4}{4}}$ $=\sqrt{\frac{9k^2+22k+5}{4}}=\sqrt{\left(\frac{9k^2+12k+4}{4}\right)+\frac{10k+1}{4}} =\sqrt{\left(\frac{3n+2}{2}\right)^2+\frac{10k+1}{4}}>\left(\frac{3n+2}{2}\right).$ Our induction is complete and the claim holds. Now plugging in $n=2023$ shows $a_{2023}\ge \frac{3(2023)-1}{2}=3034.$ Q.E.D.

This post has been edited 1 time. Last edited by PEKKA, Jun 26, 2024, 9:08 PM

Z K Y

The post below has been deleted. Click to close.

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

sami1618

885 posts

sami1618

#84 h Jul 17, 2024, 6:07 PM • 1 Y

Y by GeoKing

We show that we can not have $a_n=k$ , $a_{n+1}=k+1$ , and $a_{n+2}=k+2$ , which is sufficient. Let $s=x_1+x_2+\dots+x_n$ and $t=\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}$ . Then $k^2=st$ $(k+1)^2=(s+x_{n+1})(t+\frac{1}{x_{n+1}})\iff 2k=t\cdot x_{n+1}+s\cdot \frac{1}{x_{n+1}}$ $(k+2)^2=(s+x_{n+1}+x_{n+2})(t+\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}})\iff 2k+2=(t+\frac{1}{x_{n+1}})\cdot x_{n+2}+(s+x_{n+1})\cdot \frac{1}{x_{n+1}}$ Applying AM-GM to the third equality we must have that $t\cdot x_{n+1}=s\cdot \frac{1}{x_{n+1}}\iff x_{n+1}=\frac{\sqrt{s}}{\sqrt{t}}$ . Applying AM-GM to the fifth equality we must have that $(t+\frac{1}{x_{n+1}})\cdot x_{n+2}=$ $(s+x_{n+1})\cdot \frac{1}{x_{n+1}}\iff x_{n+2}=\frac{\sqrt{s}}{\sqrt{t}}$ , a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

Sammy27

81 posts

Sammy27

#85 h Jul 17, 2024, 9:57 PM • 1 Y

Y by Eka01

Solution

This post has been edited 3 times. Last edited by Sammy27, Jul 17, 2024, 10:14 PM

Z K Y

The post below has been deleted. Click to close.

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

dkedu

180 posts

dkedu

#86 h Jul 18, 2024, 11:33 PM

Y by

We will show that $a_{n+2} \ge a_n + 3$ which implies the result since $a_1 = 1$ .

By Cauchy-Schwarz we have $a_{n+2} = \sqrt{[(x_1+x_2+\dots+ x_n) + (x_{n+1} + x_{n+2})]\left[\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+ \frac 1{x_n} \right)+ \left(\frac{1}{x_{n+1}} + \frac{1}{x_{n+2}}\right)\right]} \ge \sqrt{(x_1+x_2+\dots+x_n)\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_n}\right)} + \sqrt{\frac{(x_{n+1} + x_{n+2})^2 }{x_{n+1}x_{n+2}}} > a_n + 2$ where the final inequality is strict since $x_{n+1} \neq x_{n+2}$ so we have the result $a_{n+2} \ge a_n + 3$ since $a_i$ is an integer for all $i$ 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.

brainfertilzer

1831 posts

brainfertilzer

#87 h Jul 20, 2024, 8:55 PM

Y by

Note that $a_1 = 1$ so it suffices to show $a_{n+2}\ge a_n + 3$ for all $n$ and we'll be done by induction. Fix $n$ and let $S = \sum_{i\le n} x_i$ and $T = \sum_{i\le n}1/x_i$ . Relabel $x_{n+1}, x_{n+2}$ as $p,q$ for convenience of typesetting. Then note that
$a_{n+2} = \sqrt{\left(S + p + q\right)\left(T + \frac{1}{p} + \frac{1}{q}\right)}\stackrel{\text{CS}}{\ge} \sqrt{ST} + \sqrt{p\cdot \frac{1}{p}} + \sqrt{q \cdot \frac{1}{q}} = a_n + 2.$ But note that equality only holds if $S/T = p/(1/p) = q/(1/q)$ . But this means $p^2 = q^2\implies p = q$ , impossible since the $x_i$ are distinct. Hence equality doesn't hold and we have $a_{n+2} > a_n + 2$ . Since the $a_i$ are integers, this means $a_{n+2}\ge a_n + 3$ as needed.

Z K Y

The post below has been deleted. Click to close.

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

N3bula

256 posts

N3bula

#88 h Sep 14, 2024, 7:14 AM

Y by

Proceed by induction, clearly we have that $a_1=1$ , I will now prove $a_{n+2}>a_{n}+2$ which gives $a_{n+2}\geq a_n+3$ .
We get:
$a_{n+2}^2=a_n^2+\left( \frac{1}{x_{n+1}} +\frac{1}{x_{n+2}} \right)(x_{n+1}+x_{n+2})+(x_{n+1}+x_{n+2})\left(\sum_{i=1}^{n}\frac{1}{x_i}\right)+\left(\frac{1}{x_{n+1}}+\frac{1}{x_{n+2}}\right)\left(\sum_{i=1}^{n}x_i\right)$ Now by two applications of am-gm and the fact $a_{n+1}\neq a_{n+2}$ we get:
$a_{n+2}^2> a_n^2+4+2a_n\sqrt{\left( \frac{1}{x_{n+1}} +\frac{1}{x_{n+2}} \right)(x_{n+1}+x_{n+2})}$ A final am-gm application gives:
$a_{n+2}^2>a_n^2+4a_n+4$ Which suffices.

Z K Y

The post below has been deleted. Click to close.

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

bobthesmartypants

4337 posts

bobthesmartypants

#89 h Sep 22, 2024, 1:48 AM

Y by

Intimidating-looking problem that ends up being not so bad at all.

We use induction to show $a_{2n-1}\ge 3n-2$ and $a_{2n}\ge 3n$ . Base cases $a_1=1$ is trivial, and $a_2\ge 3$ follows from Cauchy-Schwarz $a_2= \sqrt{(x_1+x_2)\left(\frac{1}{x_1}+\frac{1}{x_2}\right)} > 2\implies a_2\ge 3$ noting that equality case $x_1=x_2$ cannot be obtained.

Now assuming $a_{2n-1}\ge 3n-2$ and $a_{2n}\ge 3n$ , we first find by Cauchy Schwarz
$\begin{align*} a_{2n+1} &= \sqrt{(x_1+\cdots +x_{2n}+x_{2n+1})\left(\frac{1}{x_1}+\cdots + \frac{1}{x_{2n}}+\frac{1}{x_{2n+1}}\right)}\\ &= \sqrt{((x_1+\cdots +x_{2n})+x_{2n+1})\left(\frac{a_{2n}^2}{x_1+\cdots +x_{2n}}+\frac{1}{x_{2n+1}}\right)}\\ &\ge a_{2n}+1 \ge 3(n+1)-2 \end{align*}$ with equality case $x_{2n+1} = \frac{x_1+\cdots +x_{2n}}{a_{2n}}$ , as desired.

Similarly, we find $a_{2n+2}\ge a_{2n+1}+1$ with equality case $x_{2n+2} = \frac{x_1+\cdots +x_{2n+1}}{a_{2n+1}}$ . Now, the key insight is to realize that these two equality cases cannot both be true. If they were, then $x_{2n+1}$ is the average of $x_1, \ldots, x_{2n}$ and $a_{2n}-2n$ zeros. Meanwhile, since for equality case $a_{2n+1} = a_{2n}+1$ , then $x_{2n+2}$ is the average of $x_1, \ldots, x_{2n}$ and $a_{2n}-2n$ zeros and $x_{2n+1}$ , the average of these numbers, which is still just the average of these numbers. In other words, $x_{2n+2} = x_{2n+1}$ , which is disallowed. Thus, in actuality $a_{2n+2}\ge a_{2n+1}+2 \ge 3(n+1)$ as desired.

Bringing it back to the problem at hand, we get $a_{2023}\ge 3034$ .

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

573 posts

cursed_tangent1434

#90 h Dec 6, 2024, 12:47 AM

Y by

This is a really interesting problem, and I was pleasantly surprised when I managed to solve this in contest two years ago.

We proceed via induction to show that for all odd integers $n$ , $a_n \ge n + \frac{n-1}{2}$ .

First note that
$a_1 = \sqrt{x_1 \cdot \frac{1}{x_1}}=1$
Now, assume the claim is true for some odd integer $m=2k+1 \ge1$ . Throughout this proof, we will use the following key inequality,

Claim : For all positive real numbers $a$ and $b$ ,
$(a+b)\left(\frac{1}{a}+\frac{1}{b}\right) \ge 4$
Proof : This is simply Cauchy Schwarz. Note that,
$(\sqrt{a}^2 + \sqrt{b}^2)\left(\frac{1}{\sqrt{a}^2}+\frac{1}{\sqrt{b}^2}\right) \ge (1+1)^2 = 4$ as desired.

Now, we are ready for the induction. Note,
$\begin{align*} a_{m+2} &=\sqrt{(x_1+x_2+\dots+x_{m+2})\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_{m+2}}\right)}\\ a_{m+2}^2 & = (x_1+x_2+\dots+x_{m+2})\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_{m+2}}\right)\\ a_{m+2}^2 &= (x_1+x_2+\dots+x_m)\left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_m}\right) + \left(\frac{1}{x_{m+1}} +\frac{1}{x_{m+2}}\right)(x_{m+1}+x_{m+2})\\ & + (x_1+x_2 + \dots + x_m)\left(\frac{1}{x_{m+1}}+\frac{1}{x_{m+2}}\right) + \left(\frac{1}{x_1}+\frac{1}{x_2}+\dots+\frac{1}{x_m}\right)(x_{m+1}+x_{m+2})\\ & \ge (3k+1)^2 + 4 + \frac{(3k+1)^2(x_{m+1}+x_{m+2})}{x_1+x_2+\dots + x_m} + \frac{4(x_1+x_2+\dots + x_m)}{x_{m+1}+x_{m+2}}\\ & \ge (3k+1)^2 +4 + 2 \sqrt{\frac{4(3k+1)^2(x_{m+1}+x_{m+2})(x_1+x_2+\dots + x_m)}{(x_1+x_2+\dots + x_m)(x_{m+1}+x_{m+2})}}\\ & \ge (3k+1)^2 + 4(3k+1) + 4\\ & \ge (3k+3)^2\\ a_{m+2} & \ge 3k+3 \end{align*}$ But, if $a_{m+2}=3k+3$ , equality must hold at each of the above inequalities. In particular we need
$\left(\frac{1}{x_{m+1}} +\frac{1}{x_{m+2}}\right)(x_{m+1}+x_{m+2})=4$ which requires $x_{m+1}=x_{m+2}$ which is impossible if $x_1,x_2,\dots,x_{m+2}$ are pairwise distinct positive reals. Thus equality does not hold and $a_{m+2}>3k+3$ . Further since $a_{m+2}$ is an integer we must have $a_{m+2} \ge 3k+4$ so,
$a_{m+2} \ge (m+2) + \frac{m+1}{2}$ which completes the induction. Thus,
$a_{2023} \ge 2023 + \frac{2022}{2} = 3034$

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8857 posts

HamstPan38825

#91 h Dec 7, 2024, 12:04 AM

Y by

Observe that $a_1 = 1 < a_2 < \dots$ . The crux of the problem is the following claim:

Claim: There does not exist an index $n$ such that $a_{n+1} - a_n = 1$ and $a_n - a_{n-1} = 1$ simultaneously.

Proof: Suppose such an index $n$ existed. Then observe that
$\begin{align*} a_n^2 &= a_{n-1}^2 + 1 + x_n\left(\frac 1{x_1} + \frac 1{x_2} + \cdots +\frac 1{x_{n-1}}\right) + \frac 1{x_n}\left(x_1+x_2+\cdots+x_n\right) \\ &\geq a_{n-1}^2 + 1 + 2\sqrt{(x_1+x_2+\cdots+x_n)\left(\frac 1{x_1} + \frac 1{x_2} + \cdots + \frac 1{x_n}\right)} \\ &= (a_n+1)^2. \end{align*}$ Importantly, equality only holds when $x_n = \sqrt{\frac{x_1+x_2+\cdots+x_{n-1}}{\frac 1{x_1} +\frac 1{x_2}+\cdots+\frac 1{x_{n-1}}}}$ . Let $A$ and $B$ be the numerator and denominator of this quantity. The same argument applied to the index $n+1$ yields $x_{n+1} = \sqrt{\frac{A+\sqrt{\frac AB}}{B+\sqrt{\frac BA}}} = \sqrt{\frac{A\sqrt{AB}+A}{B\sqrt{AB}+B}} = \sqrt{\frac AB} = x_n$ which is a contradiction. $\blacksquare$

So in particular, $a_{n+2} - a_n \geq 3$ for each $n$ . It follows that $a_{2023} \geq 1 + 1011 \cdot 3 = 3034$ .

Z K Y

The post below has been deleted. Click to close.

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

Aiden-1089

277 posts

Aiden-1089

#92 h Jan 6, 2025, 7:06 PM

Y by

Note that $a_1=1$ . It suffices to show that $a_{n+2} \geq a_n+3$ for all $n$ .
Noting that $x_{n+1}, x_{n+2}$ are distinct,
$\begin{align*} a_{n+2}^2 &=\left(\sum_{i=1}^{n+2} x_i \right)\left(\sum_{i=1}^{n+2} \frac{1}{x_i} \right) \\ &=a_n^2 + (x_{n+1}+x_{n+2})\left(\sum_{i=1}^n \frac{1}{x_i} \right) + \left(\frac{1}{x_{n+1}} + \frac{1}{x_{n+2}} \right)\left(\sum_{i=1}^n x_i \right) + (x_{n+1}+x_{n+2})\left(\frac{1}{x_{n+1}} + \frac{1}{x_{n+2}} \right) \\ &> a_n^2 + (x_{n+1}+x_{n+2})\left(\sum_{i=1}^n \frac{1}{x_i} \right) + \left(\frac{4}{x_{n+1}+x_{n+2}} \right)\left(\sum_{i=1}^n x_i \right) + 4 \\ &\geq a_n^2 + 4 \sqrt{\left(\sum_{i=1}^n \frac{1}{x_i} \right)\left(\sum_{i=1}^n x_i \right)} + 4 =(a_n+2)^2. \end{align*}$ Since $a_{n+2}$ and $a_n$ are integers, $a_{n+2} > a_n+2 \implies a_{n+2} \geq a_n+3$ 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.

AshAuktober

970 posts

AshAuktober

#93 h Jan 15, 2025, 4:44 AM

Y by

Very beautiful problem, definitely one of the nicer algebra problems out there.
Claim 1: $a_{n+1} \ge a_n + 1$ with equality iff $x_{n+1} = \frac{x_1 + \dots + x_n}{a_n}$ .
Proof: We have
$a_{n+1} = \sqrt{a_n^2 + 1 + x_{n+1} \left(\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}\right) +\frac{ x_1 + x_2 + ... + x_n}{x_{n+1}}}$ $\stackrel{\textrm{AM-GM}}{\ge} \sqrt{a_n^2 + 1 + 2a_n} = a_n + 1.$ Equality holds iff equality holds in AM-GM, i. e.
$x_{n+1}^2 = \frac{x_1 + x_2 + ... + x_n}{\frac{1}{x_1} + \frac{1}{x_2} + ... + \frac{1}{x_n}} = \frac{ x_1 + x_2 + ... + x_n}{\frac{a_n}{ x_1 + x_2 + ... + x_n}}$ $\iff x_{n+1} = \frac{x_1 + \dots + x_n}{a_n}$ as desired. $\square$

Claim 2: We cannot simultaneously have $a_{n+2} = a_{n+1} + 1, a_{n+1} = a_n + 1$ .
Proof: Note that for equality to hold in both cases, we need
$x_{n+2} = \frac{x_1 + x_2 + \dots + x_n + x_{n+1}}{a_n + 1} = \frac{\frac{a_n+1}{a_n} \times x_1 + \dots + x_n}{a_n+1} = \frac{x_1 + x_2 + \dots + x_n}{a_n} = x_{n+1}.$ But the sequence is composed of distinct terms, so this is impossible. $\square$

Note that due to Claim 2, we must have $a_{n+2} \ge a_n + 3$ . Therefore,
$a_{2023} \ge a_{2021} + 3$ $\ge a_{2019} + 6$ $\ge a_{2017} + 9$ $\vdots$ $\ge a_1 + 3 \times 1011 = 3034$ as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

complex2math

4 posts

complex2math

#94 h Jan 25, 2025, 2:28 AM

Y by

Let $S_n := x_1 + \cdots + x_n$ and $T_n := \frac{1}{x_1} + \cdots + \frac{1}{x_n}$ , then
$\begin{aligned} a_{n + 2}^2 &= (S_n + x_{n + 1} + x_{n + 2})\left(T_n + \frac{1}{x_{n + 1}} + \frac{1}{x_{n + 2}}\right) \\ &= S_n T_n + \frac{S_n}{x_{n + 1}} + x_{n + 1}T_n + \frac{S_n}{x_{n + 2}} + x_{n + 2}T_n + \frac{x_{n+2}}{x_{n+1}} + \frac{x_{n + 1}}{x_{n+2}} + 2 \\ &\ge a_n^2 + 2a_n + 2a_n + 4 = (a_n + 2)^2 \end{aligned}$
The equality cannot hold because $x_{n + 1} \neq x_{n + 2}$ , thus $a_{n + 2} \ge a_n + 3$ and $a_{2n + 1} \ge 3n + 1$ follows easily by induction.

I am surprised that it is rated A3 on the shortlist, considering the difficulty of this problem.

Z K Y

The post below has been deleted. Click to close.

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

pie854

243 posts

pie854

#95 h Mar 5, 2025, 6:38 PM

Y by

Note that by CS: $a_n=\sqrt{(x_1+\dots+x_{n-2}+x_{n-1}+x_n)(1/x_1+\dots+1/x_{n-2}+1/x_{n-1}+1/x_n)} \geq \sqrt{(x_1+\dots+x_{n-2})(1/x_1+\dots+1/x_{n-2})}+\sqrt{x_{n-1}\cdot \frac{1}{x_{n-1}}}+\sqrt{x_n\cdot \frac{1}{x_n}}=a_{n-2}+2.$ If equality were to hold, then we would have $\frac{x_n}{1/x_n}=\frac{x_{n-1}}{1/x_{n-1}}$ i.e. $x_n=x_{n-1}$ , which is not possible. Thus, $a_n>a_{n-2}+2\implies a_n\geq a_{n-2}+3.$ By induction it follows that $a_{2023}\geq 3033+a_1=3034$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

Ilikeminecraft

330 posts

Ilikeminecraft

#97 h Mar 11, 2025, 3:58 AM

Y by

We prove the following lower bound via induction:
Claim: $a_n\geq \frac{3n + 1}{2}$
Proof: We prove $a_n \geq a_{n - 2} + 2$ with induction. First, note that $a_1 = 1.$

Now, we prove the inductive step. Observe that
$\begin{align*} a_n^2 & = a_{n - 2}^2 + \left(\frac1{x_n} + \frac1{x_{n - 1}}\right)(x_{n - 2} + x_{n - 3} + \dots + x_1) + (x_n + x_{n - 1})\left(\frac1{x_{n - 2}} + \frac1{x_{n - 3}} + \dots + \frac1{x_1}\right) + \left(\frac1{x_n} + \frac1{x_{n - 1}}\right)(x_n + x_{n - 1})\\ & \geq a_{n- 2}^2 + 4 + 2\sqrt{(x_n + x_{n - 1})\left(\frac1{x_{n - 2}} + \frac1{x_{n - 3}} + \dots + \frac1{x_1}\right)\left(\frac1{x_n} + \frac1{x_{n - 1}}\right)(x_n + x_{n - 1})} \\ & \geq a_{n - 2}^2 + 4 + 4a_{n - 2} = (a_{n - 2} + 2)^2 \end{align*}$
This finishes.

This post has been edited 1 time. Last edited by Ilikeminecraft, Mar 11, 2025, 3:59 AM

Z K Y