IMO 2023 P3

The post below has been deleted. Click to close.

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

1052 posts

#1 h Jul 8, 2023, 4:54 AM • 19 Y

Y by beansenthusiast505, aidan0626, math90, Rounak_iitr, Loppukilpailija, LoloChen, GHHardy911, GeoKing, TheBarioBario, NO_SQUARES, SatisfiedMagma, Rg230403, Amir Hossein, megarnie, Math.1234, Schur-Schwartz, qlip, abc_978, cubres

For each integer $k\geq 2$ , determine all infinite sequences of positive integers $a_1$ , $a_2$ , $\ldots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0,$ where $c_0$ , $c_1$ , \dots, $c_{k-1}$ are non-negative integers, such that $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ for every integer $n\geq 1$ .

This post has been edited 7 times. Last edited by v_Enhance, Sep 23, 2023, 2:16 AM
Reason: fix latex pet peeves

Z K Y

The post below has been deleted. Click to close.

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

aidan0626

1899 posts

aidan0626

#2 h Jul 8, 2023, 5:02 AM • 2 Y

Y by Rounak_iitr, cubres

For each integer $k\geqslant 2,$ determine all infinite sequences of positive integers $a_1,a_2,\dots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1}x^{k-1}+\cdots c_1 x+c_0,$ where $c_0,c_1,\dots,c_{k-1}$ are non-negative integers, such that
$P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ for every integer $n\geqslant 1.$

Z K Y

The post below has been deleted. Click to close.

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

navi_09220114

479 posts

navi_09220114

#3 h Jul 8, 2023, 5:04 AM • 81 Y

Y by GrantStar, Aryan-23, ihatemath123, weedtaker567, 799786, Dem0nfang, khan.academy, aidan0626, Tintarn, math90, InternetPerson10, djmathman, Supertinito, David-Vieta, numbersandnumbers, Therealway, Hexagrammum16, psi241, godjuansan, melowmolly, Anzoteh, Aoxz, TRAN THAI HUNG, steppewolf, MathLover_ZJ, MS_Kekas, qwedsazxc, PRMOisTheHardestExam, GioOrnikapa, L567, Supercali, Aimingformygoal, Creeper1612, NO_SQUARES, Assassino9931, Cty-circle, centslordm, LoloChen, Quidditch, EpicBird08, Plasma_Vortex, Filipjack, samrocksnature, megahertz13, RobertRogo, Orthogonal., Seicchi28, smartvong, Justpassingby, QWER001, ilikecats07, Rg230403, somebodyyouusedtoknow, OronSH, abrahms, rg_ryse, amir_rh, mathleticguyyy, Amir Hossein, Ankoganit, pavel kozlov, FOL, CyclicISLscelesTrapezoid, Joider, MathFan335, kamatadu, Rounak_iitr, TemetNosce, Eulermathematics, egxa, Sedro, abc_978, qiu-, stayhomedomath, qlip, DensSv, ehuseyinyigit, MS_asdfgzxcvb, cubres, giangtruong13, Mysteriouxxx

My proposal :>

Authorship comments

This post has been edited 22 times. Last edited by navi_09220114, Jul 8, 2023, 2:13 PM

Z K Y

The post below has been deleted. Click to close.

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

799786

1052 posts

799786

#4 h Jul 8, 2023, 5:56 AM • 2 Y

Y by Rounak_iitr, cubres

I think that this problem can be rephrased as a recurrence sequence, with:
$a_{n+k}=\frac{P(a_n)}{a_{n+1}...a_{n+k-1}}$
So now you only need to find ALL $P(x),a_1,a_2,...,a_{k}$ so that every following terms are integers
(And even worse, this is very tedious)
However, there is a weakness: You can prove by induction that:
$a_x=\frac{a_{x-k}P(a_{x-k})}{P(a_{x-k-1}}$

This post has been edited 3 times. Last edited by 799786, Jul 8, 2023, 6:12 AM
Reason: continue the idea

Z K Y

The post below has been deleted. Click to close.

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

numbersandnumbers

258 posts

numbersandnumbers

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

Y by Rushery_10, PRMOisTheHardestExam, Manteca, asdf334, AutomatiC__, scnwust, Rounak_iitr, Sneakyturtle, cubres

The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$ . These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$ . Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
$a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}$ and for $n > 1$ , $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$ .

First, let's handle the special case $P(x) = x^k$ ; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$ . Then, if $a_n = b$ , we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$ ; therefore $a_{n+1} = b$ . Therefore the sequence is eventually constant at $b$ ; by applying $(\star)$ we get that $a_n = b$ for all $n$ , as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$ , we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$ . Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$ , there are only finitely many $n$ with $a_n = m$ .
Proof. For every such $n$ , we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$ . Thus, if there are infinitely such $n$ , we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$ . By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$ .
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$ . But then,
$1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},$ so $a_{n+k+1} < a_{n+1}$ . Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$ , which must be less than $m$ , and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$ , we find that $a_{n'-1} > a_{n'} = m'$ , contradicting the minimality of $m$ . $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$ , so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$ . But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$ , so there must be one, call it $(d_1,\ldots,d_{k+1})$ , which appears infinitely many times. Then we must have
$P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})$ for infinitely many $n$ . By Lemma 2, this means that
$P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})$ for infinitely many $x$ , meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$ . Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$ , i.e. $d_i = id_1$ for all $i$ . As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$ , and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$ . By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b + (n-1)d_1$ for all large $n$ . If $b > 0$ , we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$ . But then $a_n \cdots a_{n+k-1} < P(1)$ , so there is no possibility for $a_{n-1}$ . So we are done in this case as well. $\square$

This post has been edited 2 times. Last edited by numbersandnumbers, Jul 8, 2023, 7:12 AM

Z K Y

The post below has been deleted. Click to close.

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

M11100111001Y1R

121 posts

M11100111001Y1R

#6 h Jul 8, 2023, 6:23 AM • 1 Y

Y by cubres

I'm not sure! Even I don't know, I'm just guessing that the proposer of this problem is Mr. Safaei from Iran. Does anyone know the proposer?

Z K Y

The post below has been deleted. Click to close.

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

navi_09220114

479 posts

navi_09220114

#7 h Jul 8, 2023, 6:24 AM • 21 Y

Y by khan.academy, JingheZhang, David-Vieta, MS_Kekas, colonel_ionut, egxa, Photaesthesia, LoloChen, TSandino, RobertRogo, khina, pavel kozlov, CyclicISLscelesTrapezoid, erringbubble, Mysteriouxxx, Illuzion, Sedro, qlip, damyan, cubres, aidan0626

I am the proposer [Ivan Chan from Malaysia]

Z K Y

The post below has been deleted. Click to close.

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

M11100111001Y1R

121 posts

M11100111001Y1R

#8 h Jul 8, 2023, 6:28 AM • 1 Y

Y by cubres

Congrats. it's a nice problem!
Thanks for telling that!

Z K Y

The post below has been deleted. Click to close.

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

blackmetalmusic

30 posts

blackmetalmusic

#9 h Jul 8, 2023, 7:24 AM • 1 Y

Y by cubres

numbersandnumbers wrote:

The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$ . These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$ . Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
$a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}$ and for $n > 1$ , $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$ .

First, let's handle the special case $P(x) = x^k$ ; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$ . Then, if $a_n = b$ , we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$ ; therefore $a_{n+1} = b$ . Therefore the sequence is eventually constant at $b$ ; by applying $(\star)$ we get that $a_n = b$ for all $n$ , as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$ , we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$ . Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$ , there are only finitely many $n$ with $a_n = m$ .
Proof. For every such $n$ , we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$ . Thus, if there are infinitely such $n$ , we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$ . By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$ .
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$ . But then,
$1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},$ so $a_{n+k+1} < a_{n+1}$ . Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$ , which must be less than $m$ , and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$ , we find that $a_{n'-1} > a_{n'} = m'$ , contradicting the minimality of $m$ . $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$ , so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$ . But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$ , so there must be one, call it $(d_1,\ldots,d_{k+1})$ , which appears infinitely many times. Then we must have
$P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})$ for infinitely many $n$ . By Lemma 2, this means that
$P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})$ for infinitely many $x$ , meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$ . Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$ , i.e. $d_i = id_1$ for all $i$ . As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$ , and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$ . By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b + (n-1)d_1$ for all large $n$ . If $b > 0$ , we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$ . But then $a_n \cdots a_{n+k-1} < P(1)$ , so there is no possibility for $a_{n-1}$ . So we are done in this case as well. $\square$

elegant solution sir
though I think this problem was kinda easy for imo#3.
it's more like a hard #2 or #5

Z K Y

The post below has been deleted. Click to close.

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

naman12

1358 posts

naman12

#10 h Jul 8, 2023, 7:29 AM • 10 Y

Y by navi_09220114, PRMOisTheHardestExam, NO_SQUARES, YaoAOPS, RobertRogo, Rounak_iitr, two_steps, axsolers_24, MS_asdfgzxcvb, cubres

Huh. This is actually surprisingly amazing of a problem and I'm honestly in love :love:

.

Main Claim. The sequence $a_n$ is increasing.
Suppose $a_n$ is a minimum of the sequence (which is possible as this is an integral sequence). If $a_n<a_{n-1}$ and $n>1$ ,
$a_{n+k}P(a_{n-1})=\prod_{i=n-1}^ka_i=a_nP(a_n)<a_nP(a_{n-1})$ as $P$ is monotonic, so $a_{n+k}<a_n$ . This is clearly impossible, so thus for any minimum, all previous terms must be equal. In particular, the sequence $a_n$ is (not necessarily strictly) increasing. $\blacksquare$

To finish, simply note that there exists some $y$ such that $P(x)<(x+y)^k$ ; for example,
$y>\text{max}\left(\frac{c_j}{\binom kj}\right)$ This implies that since $a_n\leq a_{n+1}<a_n+y$ , we have
$(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})\in [0,y]^{k+1}$ by the Pigeonhole Principle, some value $(a'_1,\ldots,a'_{k+1})$ appears infinitely often. Call $n$ good if $(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})=(a'_1,\ldots,a'_{k+1})$ . Then,
$P(x)=\prod_{j=1}^k\left(x+\sum_{i=1}^ja'_i\right)=\prod_{j=1}^k\left(x+\sum_{i=2}^{j+1}a'_i\right)$ for infinitely many values of $x$ (which comes from taking $x=a_n,a_{n+1}$ where $n$ is good), so thus these factors must be equal up to permutation. However, as $a'_i\geq 0$ , we know $a'_i=a'_{i+1}$ , so $a'_i$ is constant. This means that $a_i$ is an arithmetic sequence, and clearly it is a non-decreasing one.

Motivation
Remarks
A note on difficulty

This post has been edited 1 time. Last edited by naman12, Jul 8, 2023, 7:50 AM

Z K Y

The post below has been deleted. Click to close.

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

799786

1052 posts

799786

#11 h Jul 8, 2023, 7:48 AM • 1 Y

Y by cubres

Uh, finally solved this problem. Since my solution is quite the same as #5, I'll just leave some thoughts here.
First, this was very fun to solve tho. Even though the solution is fairly short, it's not easy to find. I enjoyed this problem a lot, so I think this is a very appropriate P3 problem. Just wished this was a little harder

Z K Y

The post below has been deleted. Click to close.

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

navi_09220114

479 posts

navi_09220114

#12 h Jul 8, 2023, 8:00 AM • 3 Y

Y by RobertRogo, Rounak_iitr, cubres

naman12 wrote:

Huh. This is actually surprisingly amazing of a problem and I'm honestly in love :love:

.

Main Claim. The sequence $a_n$ is increasing.
Suppose $a_n$ is a minimum of the sequence (which is possible as this is an integral sequence). If $a_n<a_{n-1}$ and $n>1$ ,
$a_{n+k}P(a_{n-1})=\prod_{i=n-1}^ka_i=a_nP(a_n)<a_nP(a_{n-1})$ as $P$ is monotonic, so $a_{n+k}<a_n$ . This is clearly impossible, so thus for any minimum, all previous terms must be equal. In particular, the sequence $a_n$ is (not necessarily strictly) increasing. $\blacksquare$

To finish, simply note that there exists some $y$ such that $P(x)<(x+y)^k$ ; for example,
$y>\text{max}\left(\frac{c_j}{\binom kj}\right)$ This implies that since $a_n\leq a_{n+1}<a_n+y$ , we have
$(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})\in [0,y]^{k+1}$ by the Pigeonhole Principle, some value $(a'_1,\ldots,a'_{k+1})$ appears infinitely often. Call $n$ good if $(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})=(a'_1,\ldots,a'_{k+1})$ . Then,
$P(x)=\prod_{j=1}^k\left(x+\sum_{i=1}^ja'_i\right)=\prod_{j=1}^k\left(x+\sum_{i=2}^{j+1}a'_i\right)$ for infinitely many values of $x$ (which comes from taking $x=a_n,a_{n+1}$ where $n$ is good), so thus these factors must be equal up to permutation. However, as $a'_i\geq 0$ , we know $a'_i=a'_{i+1}$ , so $a'_i$ is constant. This means that $a_i$ is an arithmetic sequence, and clearly it is a non-decreasing one.

Motivation
Remarks
A note on difficulty

I really love your remarks there: its pretty much what I felt when I solved the problem - the properties are rather surprising for me as well!

Z K Y

The post below has been deleted. Click to close.

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

Rg230403

222 posts

Rg230403

#13 h Jul 8, 2023, 8:05 AM • 2 Y

Y by PRMOisTheHardestExam, cubres

numbersandnumbers wrote:

The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$ . These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$ . Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
$a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}$ and for $n > 1$ , $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$ .

First, let's handle the special case $P(x) = x^k$ ; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$ . Then, if $a_n = b$ , we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$ ; therefore $a_{n+1} = b$ . Therefore the sequence is eventually constant at $b$ ; by applying $(\star)$ we get that $a_n = b$ for all $n$ , as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$ , we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$ . Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$ , there are only finitely many $n$ with $a_n = m$ .
Proof. For every such $n$ , we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$ . Thus, if there are infinitely such $n$ , we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$ . By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$ .
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$ . But then,
$1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},$ so $a_{n+k+1} < a_{n+1}$ . Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$ , which must be less than $m$ , and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$ , we find that $a_{n'-1} > a_{n'} = m'$ , contradicting the minimality of $m$ . $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$ , so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$ . But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$ , so there must be one, call it $(d_1,\ldots,d_{k+1})$ , which appears infinitely many times. Then we must have
$P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})$ for infinitely many $n$ . By Lemma 2, this means that
$P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})$ for infinitely many $x$ , meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$ . Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$ , i.e. $d_i = id_1$ for all $i$ . As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$ , and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$ . By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b + (n-1)d_1$ for all large $n$ . If $b > 0$ , we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$ . But then $a_n \cdots a_{n+k-1} < P(1)$ , so there is no possibility for $a_{n-1}$ . So we are done in this case as well. $\square$

This proof is really nice, I did not see the clever argument for Lemma 3 presented in this solution so I had the following solution:

I have skipped the proof of claims that the $a_i$ get arbitrarily large in the following writeup.

Let $s_1< s_2< \dots$ be an inifinite sequence such that $a_{s_i}\le a_{s_{i+j}}$ for all $j\in \{1,2,\dots k\}$ . Now, $a_{s_i}^{k-1}(a_{s_i}+c_0+c_1+\dots c_{k-1})\prod\limits_{j=1}^k a_{s_{i+j}}\ge a_{s_i}^k$ . Thus, $|a_{s_{i+j}}-a_{s_i}|\le c_0+c_1+\dots c_{k-1}$ . Thus, from each $s_i$ term, consider the polynomial: $P_i(x)=\prod\limits_{i=1}^k (x+a_{s_i+j}-a_{s_i})$ .

By infinite pigeonhole principle, infinitely many of these polynomials are the same. Let's call one such polynomial occuring infinitely many times $S_1(x)$ . Now, for infinitely many values of $x$ , we have $P(x)=S_1(x)$ . Thus, $P(x)=(x+d_1)(x+d_2)\dots (x+d_k)$ for some $d_1, \dots d_k \ge 0$ and infinitely many times we have $a_{s_i}+d_j=a_{s_{i+j}}$ all occuring simultaneously. Let the infinite sequence of $s_i$ with previous property be $t_1<t_2 \dots$ .

Now, $P(a_{t_i+1})=\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)$ and thus, $a_{t_i+k+1}=\dfrac{\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)}{\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)}\cdot a_{t_i+1}$
Thus, again $a_{t_i+k+1}-a_{t_i+1}$ is bounded and we have that polynomials $Q_i(x)=\prod\limits_{j=1}^k(x+a_{t_i+j}-a_{t_i})$ have the same polynomial occuring infinitely many times. Thus, we get a polynomial $S_2(x)$ which occurs infinitely many times of the form $(x+r_1)(x+r_2)\dots (x+r_k)$ but this must be $P(x)$ . Thus, ${d_1,d_2,\dots d_k}-{d_1}={0,d_1,\dots d_k}\setminus {d_t}$ for some $t$ . Thus, the $d_i$ form an AP in some order with common difference $d_1$ . Thus the polynomial is $(x+d)(x+2d)\dots (x+kd)$ .

Now, for each $t_i$ , consider the lowest $l_i$ such that $t_{i+l_i}-t_i\ne l_id$ . If such $l_i$ exist infinitely often then amongst each of these, we again have that $|t_{i+l_i}-t_{i+l_i+j}|$ is bounded for $j\in \{1,2,\dots k\}$ . Thus repeating our previous argument, we get that $t_{i+l_i+j}-t_{l_i} > 0$ for all $j$ but $t_{i+l_i}-t_i\ne l_i d$ , thus we get that for some $j>l_i$ , we have $t_{i+j}-t_{i+l_i} =l_id$ which implies $t_{i+j} \le t_{l_i+j}$ which is a contradiction.

Thus, such $l_i$ do not exist infinitely often. Thus, there is a term $t_i$ such that $a_{t_i+j}-a_{t_i}=jd$ for all $j\in {1,2,\dots k}$ and polynomial is $(x+d)(x+2d)\dots (x+kd)$ and using this we can induct on the sequence in both directions to find that if forms the required AP with common difference $d$ . Thus, we are done!

I really liked the problem and don't really have much more to remark which is different from the previous comments. I do believe that it's on an easier side of P3s but that does not make it inappropriate for the position. The best way to judge is to just wait for the statistics to come out

This post has been edited 2 times. Last edited by Rg230403, Jul 8, 2023, 8:12 AM

Z K Y

The post below has been deleted. Click to close.

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

Complete_quadrilateral

144 posts

Complete_quadrilateral

#14 h Jul 8, 2023, 8:38 AM • 1 Y

Y by cubres

Claim 1:
$A$ is either unbounded or constant.
Proof
Claim 2:
$A$ is nondecreasing
Proof
So if $A$ is not constant we get that at some point all numbers after some $a_N$ are $a_N+O(1)$ . Now if we have that set of $a_{N+k}-a_N$ is not always the same after some point we get that there are at least two of such sets appearing infinitely many times, call them $S$ and $S'$ , so $P(x)=\Pi_{p\in S}(x+p)=\Pi_{q\in S'}(x+q)$ , contradiction, so that set is fixed after some arbitrarily big $a_N$ .
Claim: This set is an arithmetic progression
Proof
Now we know that $A$ is an arithmetic progression after some point so $P(x)=\Pi_{i=1}^{i=k} (x+ti)$ . Now we can just go backwards and get that $A$ was an arithmetic progression all along.
Comment

This post has been edited 2 times. Last edited by Complete_quadrilateral, Jun 19, 2024, 7:20 AM

Z K Y

The post below has been deleted. Click to close.

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

Anzoteh

126 posts

Anzoteh

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

Y by PRMOisTheHardestExam, GeoKing, navi_09220114, cubres

navi_09220114 wrote:

It all started with a desperate need for NT problems in our country's TST lol. My friend Anzo gave me a bootleg of 2015 A1:

"Let $a_0$ be arbitrary postive real, $a_{n + 1} = \frac{(n + 2)a_n}{(a_n^2 + n + 1)}$ . Determine $\lim_{n \rightarrow \infty} (a_1 + ... + a_n) - n$ in terms of $a_0$ ."

OMG I'm so honored to be featured by the proposer himself :-D

It is a very beautiful problem, and no, I haven't solved it yet. One more thing to add into my bucket list!

navi_09220114 wrote:

Meanwhile, the NT we used for the TST is here lol: (It's simple but nice so do try it!)

"Do there exist infinitely many triples of positive integers $(a, b, c)$ such that $a$ , $b$ , $c$ are pairwise coprime, and $a! + b! + c!$ is divisible by $a^2 + b^2 + c^2$ ?"

This was Malaysian TST P4 this year, and it's mine. (Could have been a borderline P5 tbh).

Z K Y

The post below has been deleted. Click to close.

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

bhan2025

96 posts

bhan2025

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

Y by GeoKing, cubres

Main Claim) $a_1$ must be the minimum value of sequence $a$
pf) There obviously must exist a minimum value of sequence $a$ , as the sequence is restricted to positive integers.
Assume $a_1$ is not the minimum. In other words, there exists $a_i$ ( $i \neq 1$ ) such that $a_i$ is the minimum of $a$ . Let $a_i$ be the first of such minimum values. Then, we can safely say that $a_{i-1} > a_i$ .
We know that $P(a_{i-1}) = a_i a_{i+1} \ldots a_{i+k-1}$ and $P(a_i) = a_{i+1} a_{i+2} \ldots a_{i+k}$ . Since $P(a_{i-1}) > P(a_i)$ , this means that $a_i > a_{i+k}$ .
However, since we set $a_i$ as the minimum value of $a$ this causes a contradiction.

Corollary of Main Claim) $a$ is a nondecreasing sequence
Explanation: Claim 1 essentially states that for any positive integer $n$ , the minimum value of $a_{[n,\infty)}$ is $a_n$ . Thus, using induction with $n = 1, 2, \ldots$ shows that $a$ must be nondecreasing.

We now split the proof into two cases:

$\textbf{Case 1}$ ) $a$ has a maximum value
This means that there exists some positive integer $n$ such that for all $i \geq n$ , $a_i = w$ ( $w$ is a constant)
Thus, $P(w) = w^k$ , implying that $P(x) = x^k$ . Therefore, $P(a_{n-1}) = (a_{n-1})^k = a_n a_{n+1} \ldots a_{n+k-1} = w^k$ , which means that $a_{n-1} = w$ . Repeating this logic for $n-2, n-3, \ldots, 1$ shows that $a_i = w$ for all $i$ . We have obtained our first solution.

$\textbf{Case 2}$ ) $a$ doesn't have a maximum value
This means that sequence $a_i$ increases indefinitely as $i$ increases

Claim) $a$ is strongly increasing
Assume $a_i = a_{i+1}$ for some $i$ . Since $P(a_i) = P(a_{i+1})$ , we can see that $a_{i+1} = a_{i+k+1}$ . Since $a$ is nondecreasing, this means that all numbers $a_i$ through $a_{i+k+1}$ are equal. Repeating this logic while increasing $i$ shows that $a$ becomes a constant sequence, causing a contradiction.

Let $Seq(i) = (a_{i+1}-a_i, a_{i+2} -a_i, \ldots, a_{i+k}-a_i)$ . $Seq(i,j)$ denotes the $j$ th element in the $k$ -element permutation $Seq(i)$
Set $N$ as a very, very large positive integer. Then, we can safely say that all $a_i$ for $i>N$ is close to infinity as $a$ has no upper bound.

Claim 2) For all $i>N$ $Seq(i)$ must be a constant
pf) Assume $Seq(i) \neq Seq(i+1)$ for some very large $i > N$
Let $P_1(x) = \Pi_{j=1}^k (x + Seq(i)(j))$ and $P_2(x) = \Pi_{j=1}^k (x + Seq(i+1)(j))$ .
Then, we can see that $P(a_i) = P_1(a_i)$ and $P(a_{i+1}) = P_2(a_{i+1})$ . Since $P_1 \neq P_2$ , at least one of the functions $P - P_1$ and $P - P_2$ cannot be a zero function with all coefficients equal to $0$ . WLOG, assume that $P - P_1$ is nonnegative.
Since both $P$ and $P_1$ have nonnegative coefficients, $P - P_1$ cannot have any coefficients that are larger than $max(c_0,c_1,\ldots,c_{k-1})$ . However, since we set $a_i$ as a very, very large positive integer it cannot be a solution of $P - P_1$ . Thus, there is a contradiction.

Thus, $Seq(i)$ eventually becomes constant for $i > N$ , which means $a$ must be an arithmetic sequence (this is trivial by induction working backwards from $N$ to $1$ ). We have obtained our second solution.

Note: The explanation for Claim 2 definitely could be improved (it is possible a very large negative coefficient in $P_1$ overrides the large value of $a_i$ ), but the intuition should be very clear.

Additional bound to address logical hole in Claim 2
Remarks on Question and Solution

This post has been edited 3 times. Last edited by bhan2025, Jul 14, 2023, 11:51 AM
Reason: last remarks

Z K Y

The post below has been deleted. Click to close.

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

Marinchoo

407 posts

Marinchoo

#45 h Jul 18, 2023, 8:38 AM • 2 Y

Y by PRMOisTheHardestExam, cubres

Here's my submission at the IMO. I missed the slick finish from the official solution, though I think my approach is much more motivated. The answer is all infinite arithmetic progressions of positive integers. These work because if $a_{n} = \lambda_{1} + (n-1)\lambda_{2}$ for some integers $\lambda_{1} >0$ , $\lambda_{2} \geq 0$ we can pick $P(x) = (x+\lambda_{2})(x+2\lambda_{2})\cdots(x+k\lambda_{2})$ and the polynomial identity will be satisfied. We show that no other sequences work.

Main claim. The key step is recognizing that the sequence $\{a_{i}\}_{i=1}^{\infty}$ is strictly increasing if it's not constant.

Proof: The idea is to show that if $d = \min_{m \in \mathbb{N}} a_{m}$ and there exists some $t > 1$ with $a_{t} = d$ , then the sequence is constant. Assume that's not the case. If $a_{t-1} > d$ , compare $P(a_{t-1})$ and $P(a_{t})$ :
$a_{t+1}a_{t+2}\cdots a_{t+k} = P(a_{t}) < P(a_{t-1}) = a_{t}a_{t+1}\cdots a_{t+k-1} \Longrightarrow a_{t+k} < a_{t} = d = \min_{m\in\mathbb{N}} a_{m}$ with the inequality holding true due to all the $c_{i}$ being nonnegative. The last inequality $a_{t+k-1} < d$ is clearly impossible, so we derive a contradiction in this case. If $a_{t-1} = d$ , comparing $P(a_{t-1})$ and $P(a_{t})$ implies that $a_{t+k} = a_{t} = d$ and we just proved that if $a_{i} = d$ for $i>1$ , then $a_{i-1} = d$ as well, we get that $a_{t-1} = a_{t} = a_{t+1} = \cdots = a_{t+k} = d$ by backwards induction from $a_{t+k} = d$ . Repeating this argument for $a_{t}$ and $a_{t+1}$ we get that $a_{t+k+1} = d$ as well and continuing on forward, the sequence $\{a_{i}\}_{i>t-2}$ is constant. We can also show that the beginning of the sequence attains that same constant value:
$a_{t-1}a_{t-1}\cdots a_{t+k-2} = P(a_{t-2}) \geq P(d) = P(a_{t-1}) = a_{t}a_{t+1}\cdots a_{t+k-1}$ However, the leftmost and rightmost expressions are both equal to $d^{k}$ which is possible only if $a_{t-2} = d$ . Inducting downward, we get that $a_{t-3} = d$ and so on as well, so the sequence is indeed constant. Thus we've proven that $a_{1} = d$ and $a_{1} < a_{i}$ for all $i>1$ . It remains to be noticed that if $\{a_{i}\}_{i=1}^{\infty}$ satisfies the desired condition, then we can delete the first few terms of the sequence without any problem, so the above argument also shows that $a_{2} < a_{i}$ for all $i>2$ and so on, $a_{1} < a_{2} < a_{3} < \cdots$ , hence the sequence is indeed strictly increasing.

Structure claim. There exist integers $0 < m_{1} < m_{2} < \dots < m_{k}$ such that $P(x) = (x+m_{1})(x+m_{2})\cdots (x+m_{k})$ .

Proof: Let $S = \sum\limits_{i=0}^{k-2} c_{i}$ . Call a positive integer $n$ big if $n>S$ . For all big integers, we have that $P(n) < n^{k} + (c_{k-1}+1)n^{k-1}$ as
$P(n) = n^{k} + c_{k-1}n^{k-1} + \sum\limits_{i=0}^{k-2} c_{i}n^{i} \leq n^{k} + c_{k-1}n^{k-1} + n^{k-2}\sum\limits_{i=0}^{k-2} c_{i} < n^{k} + (c_{k-1}+1)n^{k-1}$ As the sequence is strictly increasing, all but finitely many of the $a_{i}$ are not big. Denote $b_{i,j} = a_{i} - a_{j} > 0$ for $i>j$ . For big $a_{i}$ , we have that
$a_{i}^{k} + (c_{k-1}+1)a_{i}^{k-1} > P(a_{i}) = \prod\limits_{j=1}^{k} (a_{i}+b_{i+j, i}) > a_{i}^{k} + b_{i+j, i}a_{i}^{k-1}$ For any $1\leq j\leq k$ . Thus $b_{i+j, i} \leq c_{k-1}$ , so the differences $a_{i+1} - a_{i}$ are bounded by a constant for big $a_{i}$ . Therefore the $k$ -tuple $(b_{i+1, i}, b_{i+2, i}, \cdots, b_{i+k, i})$ can take on finitely many (at most $c_{k-1}^{k}$ ) values, so by the PHP there exists a tuple $(e_{1}, e_{2}, \cdots, e_{k})$ such that
$P(a_{i}) = (a_{i} + e_{1})(a_{i} + e_{2}) \cdots (a_{i} + e_{k})$ holds for infinitely many positive integers $i$ . This forces the polynomial $P(x) - \prod\limits_{i=1}^{k} (x+e_{i})$ to have infinitely many distinct real roots, hence must be the constant zero and the claim is proved as clearly $e_{1} < e_{2} < \cdots < e_{k}$ because the sequence $\{a_{i}\}$ is strictly increasing.

Finish. We first show that $m_{i+1} - m_{i}$ is constant and then that $a_{i+1} - a_{i}$ is constant.

Proof: We work with sufficiently large $a_{i}$ . Notice that:
$a_{n}^{k-1} < a_{n+2}a_{n+3}\cdots a_{n+k} \leq \gcd(P(a_{n}), P(a_{n+1})) \leq \prod\limits_{i=1}^{k} \gcd(a_{n}+m_{i}, P(a_{n+1}) ) \leq \prod\limits_{i=1}^{k} \prod\limits_{j=1}^{k} \gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ Consider a $k \times k$ table with entiries $\gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ in the cell $(i, j)$ . For a fixed $i$ consider the quantity $\gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ ranging over all $j$ . Notice that since $n$ is big, we have that:
$a_{n+1}+m_{j}-a_{n}-m_{i} = m_{j} + b_{n+1, n} - m_{i} \leq 2c_{k-1}-1$ hence if $a_{n}+m_{i} \neq a_{n+1}+m_{j}$ , their gcd is bounded from above by a constant. This impies that there's at most one entry $a_{n}+m_{i} < 2a_{n}$ (because $n$ is sufficiently large and $b_{n+i, n}$ is bounded) in the $i$ -th row and all other entries must be at most some constant $C = 2c_{k-1}-1$ . However, notice that for any $j$ we have:
$a_{n}+b_{n+1, n} = a_{n+1} < a_{n+1} + m_{j}$ therefore the product of the entries in the first row is bounded by $C^{k}$ . Now, for the remaining $k-1$ rows, if we assume that for some $i$ there doesn't exist a $j$ such that $a_{n}+m_{i} = a_{n+1} + m_{j}$ , then the product of all entries is bounded from above by
$C^{2k}\cdot 2^{k-2} \cdot a_{n}^{k-2} < a_{n}^{k-1}$ for sufficiently large $n$ which is a contradiction with the previously established inequality. Hence for every $i>1$ there exists a $j$ such that $a_{n}+m_{i} = a_{n+1}+m_{j}$ . Clearly $j = k$ is too big to satisfy such an equality for any $i\leq k$ , but also
$m_{2} < m_{3} < \cdots < m_{k}$ $m_{1} < m_{2} < \cdots < m_{k-1}$ hence we must have $a_{n} + m_{i} = a_{n+1} + m_{i-1}$ . This shows that
$0 = (a_{n} + m_{i}) - (a_{n+1} + m_{i-1}) = (a_{n}-a_{n+1}) - (m_{i-1}-m_{i})$ proving that $m_{i} - m_{i-1}$ is constant, say $m_{i} - m_{i-1} = L$ and furthermore, for sufficiently large $n$ we have that $a_{n+1}-a_{n} = L$ , hence the sequence is eventually an arithmetic progression. Having that in mind, assume that $\{a_{n}\}_{n\geq N}$ is an arithmetic progression. Then
$P(a_{N-1}) = a_{N}a_{N+1}\cdots a_{N+k} = \prod\limits_{i=1}^{k} (a_{N}+L(i-1)) = P(a_{N}-L)$ which implies that $a_{N-1} = a_{N} -L$ as all the coefficients of $P$ are nonnegative, so if $a<b$ , then $P(a) < P(b)$ . Inducting downward, in the same manner, shows that every element of the sequence must be part of this increasing arithmetic progression. We showed that these sequences work, so the problem is solved.
Remarks

Z K Y

The post below has been deleted. Click to close.

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

GrantStar

821 posts

GrantStar

#46 h Jul 20, 2023, 7:38 PM • 2 Y

Y by PRMOisTheHardestExam, cubres

ridiculous (shows my alg skill issue, took like >4 hours not including customizing text editor colors so my eyes weren't murdered every time i tried to write this up)

Attachments:

2022 IMO3.pdf (150kb)

Z K Y

The post below has been deleted. Click to close.

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

ABCDE

1963 posts

ABCDE

#47 h Aug 6, 2023, 11:59 AM • 4 Y

Y by navi_09220114, khina, v_Enhance, cubres

It would be interesting to relax some of the conditions in this problem, but it seems like pretty much all of them are necessary to make the problem tractable.

Th3Numb3rThr33 wrote:

My solution is the same as everyone else’s. Here is a solution path by observing the strength of the conditions in the problem statement, at least for $k=2$ .

The sequence $a$ , $b$ , $c$ , $a$ , $b$ , $c$ , $a$ , $\ldots$ works if we let $P(x) = x^2 -(a+b+c)x+(ab+bc+ca)$ , so we must use the fact that all coefficients of $P$ are nonnegative. This suggests that $P$ monotonically increasing is important (which we can use to show $a_i$ nondecreasing).
The sequence $1$ , $2$ , $4$ , $8$ , $\ldots$ works if we let $P(x) = 8x^2$ , so we must use the fact that $P$ is monic. This suggests that something like $x^{-k+1}P(x) - x$ is bounded is important (which we can use to show $a_{i+1}-a_i$ bounded).

Then the finish is by the same Pigeonhole argument on “constellations” as everyone else.

Adding onto the list of pathological examples, even if we only allow $a_i$ to be arbitrary integers rather than nonnegative and keep all other conditions, we suddenly obtain uncountably many solutions for $k=2m$ even: given any positive integers $r_1,\ldots,r_{2m}$ , we may arbitrarily concatenate $0,-r_{\pi_1},\ldots,-r_{\pi_{2m}}$ for arbitrary permutations $\pi$ of $1,\ldots,2m$ , and this sequence will work for the polynomial $P(x)=(x+r_1)\cdots(x+r_{2m})$ . Similarly, for any positive integers $r_1,\ldots,r_{k-1}$ , any sequence consisting of elements of $\{0,-r_1,\ldots,-r_{k-1}\}$ with no consecutive block of nonzero integers of length $k$ will work for the polynomial $P(x)=x(x+r_1)\cdots(x+r_{k-1})$ .

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6877 posts

v_Enhance

#48 h Sep 23, 2023, 2:36 AM • 8 Y

Y by GrantStar, aidan0626, megarnie, PRMOisTheHardestExam, Rounak_iitr, math90, Sedro, cubres

Solution from Twitch Solves ISL:

The answer is $a_n$ being an arithmetic progression. Indeed, if $a_n = d(n-1) + a_1$ for $d \ge 0$ and $n \ge 1$ , then $a_{n+1} a_{n+2} \dots a_{n+k} = (a_n+d)(a_n+2d)\dots(a_n+kd)$ so we can just take $P(x) = (x+d)(x+2d) \dots (x+kd)$ .
The converse direction takes a few parts.
Claim: Either $a_1 < a_2 < \cdots$ or the sequence is constant.
Proof. Note that $\begin{align*} P(a_{n-1}) &= a_{n}a_{n+1}\cdots a_{n+k-1} \\ P(a_n) &= a_{n+1}a_{n+2}\cdots a_{n+k} \\ \implies a_{n+k} &= \frac{P(a_n)}{P(a_{n-1})} \cdot a_n. \end{align*}$ Now the polynomial $P$ is strictly increasing over ${\mathbb N}$ .
So assume for contradiction there's an index $n$ such that $a_n < a_{n-1}$ . Then in fact the above equation shows $a_{n+k} < a_n < a_{n-1}$ . Then there's an index $\ell \in [n+1,n+k]$ such that $a_\ell < a_{\ell-1}$ , and also $a_\ell < a_n$ . Continuing in this way, we can an infinite descending subsequence of $(a_n)$ , but that's impossible because we assumed integers.
Hence we have $a_1 \le a_2 \le \cdots$ . Now similarly, if $a_n = a_{n-1}$ for any index $n$ , then $a_{n+k} = a_n$ , ergo $a_{n-1} = a_n = a_{n+1} = \dots = a_{n+k}$ . So the sequence is eventually constant, and then by downwards induction, it is fully constant. $\blacksquare$

Claim: There exists a constant $C$ (depending only $P$ , $k$ ) such that We have $a_{n+1} \leq a_n + C$ .
Proof. Let $C$ be a constant such that $P(x) < x^k + Cx^{k-1}$ for all $x \in {\mathbb N}$ (for example $C = c_0 + c_1 + \dots + c_{k-1} + 1$ works). We have $\begin{align*} a_{n+k} &= \frac{P(a_n)}{a_{n+1} a_{n+2} \dots a_{n+k-1}} \\ &< \frac{P(a_n)}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\ &< \frac{a_n^k + C \cdot a_n^{k-1}}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\ &< a_n + C + 1. \end{align*}$ $\blacksquare$
Assume henceforth $a_n$ is nonconstant, and hence unbounded. For each index $n$ and term $a_n$ in the sequence, consider the associated differences $d_1 = a_{n+1} - a_n$ , $d_2 = a_{n+2} - a_{n+1}$ , \dots, $d_k = a_{n+k}-a_{n+k-1}$ , which we denote by $\Delta(n) \coloneqq (d_1, \dots, d_k).$ This $\Delta$ can only take up to $C^k$ different values. So in particular, some tuple $(d_1, \dots, d_n)$ must appear infinitely often as $\Delta(n)$ ; for that tuple, we obtain $P(a_N) = (a_N+d_1)(a_N+d_1+d_2) \dots (a_N+d_1+\dots+d_k)$ for infinitely many $N$ . But because of that, we actually must have $P(X) = (X+d_1)(X+d_1+d_2) \dots (X+d_1+\dots+d_k).$ However, this also means that exactly one output to $\Delta$ occurs infinitely often (because that output is determined by $P$ ). Consequently, it follows that $\Delta$ is eventually constant. For this to happen, $a_n$ must eventually coincide with an arithmetic progression of some common difference $d$ , and $P(X) = (X+d)(X+2d) \dots (X+kd)$ . Finally, this implies by downwards induction that $a_n$ is an arithmetic progression on all inputs.

Z K Y

The post below has been deleted. Click to close.

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

thdnder

198 posts

thdnder

#49 h Feb 11, 2024, 8:49 AM • 3 Y

Y by Iveela, MS_asdfgzxcvb, cubres

Answer: Any arithmetic progression satisfies the problem condition.

Firstly, let $(a_n)_{n\ge 1}$ be an arithmetic progression with difference $d$ . Then taking $P(x) = (x+d)(x+2d)\cdots (x+dk)$ works.

Now we'll prove that the sequence $(a_n)_{n\ge 1}$ is an arithmetic progression. Consider the following claim:

Claim: $a_n \le a_{n+1}$ for all $n \ge 1$ .

Proof. Assume the contrary, $a_n > a_{n+1}$ for some $n$ . Then note that $P$ increases on $[0, \infty)$ , hence $P(a_n) > P(a_{n+1})$ , which means $a_{n+1}a_{n+2}\cdots a_{n+k} > a_{n+2}a_{n+3}\cdots a_{n+k+1}$ , or equivalently $a_{n+1} > a_{n+k+1}$ . Hence there exists $n_1$ such that $a_{n_1} > a_{n_1+1} \le a_{n_1+2} \le \dots \le a_{n+k+1}$ . Thus $a_{n_1+1} < a_{n+k+1} < a_{n+1} < a_{n}$ , so replacing $n \to n_1$ and repeating the same argument on $n_1$ , we get there exists $n_2$ such that $a_{n_2} > a_{n_2+1}$ and $a_{n_2+1} < a_{n_1+1} < a_{n+1}$ . Thus repeating same argument over and over, we get there exists an increasing sequence $(n_k)_{k\ge 0}$ such that $a_{n_i+1} > a_{n_{i+1}+1}$ for all $i \ge 0$ , so $a_{n_0+1} > a_{n_1+1} > a_{n_2+1} > \dots >$ , contradicting the fact that the sequence $(a_n)_{n\ge 1}$ takes positive integer values. $\blacksquare$

Thus by claim, $a_{n+i} - a_n \ge 0$ for all $1 \le i \le k$ .

Claim: $a_{n+k} - a_n$ is bounded above.

Proof. Suppose $a_{n+k} - a_n$ takes arbitrarily large values. Since $\deg(P) = k$ , so there exists $c$ such that $P(x) < (x+c)^k$ for all $x > 0$ . Let $N$ be a sufficiently large integer. Then there exists $n$ such that $a_{n+k} - a_n \ge N$ . So $a_n^k + N \cdot a_n^{k-1} = a_n^{k-1}(a_n+N) \le a_{n+1}a_{n+2}\cdots a_{n+k} = P(a_n) < (a_n+c)^k$ , contradicting $N$ is sufficiently large. $\blacksquare$

Let $S_n$ be $k-$ tuplet of integers $(a_{n+1} - a_n, a_{n+2} - a_n, \dots, a_{n+k} - a_n)$ . We say that tuplets $(a_1, a_2, \dots, a_k)$ and $(b_1, b_2, \dots, b_k)$ are equal if and only if $a_i = b_i$ for $1 \le i \le k$ . Then by claim, all integers in any tuplets doesn't exceed a certain integer, so by infinite pigeonhole principle, there exists an increasing sequence $(i_n)_{n\ge 1}$ such that $S_{i_1} = S_{i_2} = \dots$ . Let $d_j = a_{i_1 + j} - a_{i_1}$ for $1 \le j \le k$ and let $Q(x) = (x+d_1)(x+d_2)\cdots (x+d_k)$ . Then we have $Q(a_{i_n}) = P(a_{i_n})$ for all $n \ge 1$ , which means $a_{i_n}$ is root of $P(x) - Q(x)$ , which means $P(x) = Q(x)$ or the sequence $(a_n)_{n\ge 1}$ is eventually constant. If the sequence $(a_n)_{n\ge 1}$ is eventually constant, then $P(x) = x^k$ and backward induction shows that $(a_n)_{n\ge 1}$ is constant sequence. Thus we can assume $(a_n)_{n\ge 1}$ is nonconstant sequence, and thus we get $P(x) = Q(x) = (x+d_1)(x+d_2)\cdots (x+d_k)$ . If there exists an increasing sequence $(j_n)_{n\ge 1}$ such that $S_{j_1} = S_{j_2} = \dots$ and $S_{j_1} \neq S_{i_1}$ , then we get $\prod_{a \in S_{i_1}}(x+a) = P(x) = \prod_{a \in S_{j_1}}(x+a)$ , which is an evident contradiction. Hence for sufficiently large integer $n$ , we get $S_n = S_{i_1}$ . Therefore $a_{n+i} - a_n = d_i$ for all sufficiently large integer $n$ , which means $d_i + d_j = d_{i+j}$ for all $1 \le i, j \le k$ satisfying $i + j \le k$ , which shows that $d_i = i \cdot d$ for some $d \ge 0$ . Thus the sequence $(a_n)_{n\ge 1}$ eventually becomes an arithmetic progression. Now backward induction shows that $(a_n)_{n\ge 1}$ is an arithmetic progression, as required. $\blacksquare$

This post has been edited 1 time. Last edited by thdnder, Jun 16, 2024, 6:19 AM

Z K Y

The post below has been deleted. Click to close.

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

pi271828

3369 posts

pi271828

#50 h Mar 29, 2024, 1:27 AM • 2 Y

Y by Rounak_iitr, cubres

We will prove that the only sequences that work are arithmetic sequences.

Claim: $a_n$ is non-decreasing

Let $a_i$ be a minimum of the sequence. If $a_1$ is a unique minimum, then "delete" this term, shift indices down by $1$ , and repeat the process. If the process repeats infinitely than obviously $a_n$ is non-decreasing. If not however, then we proceed with the following. We have $a_iP(a_i) = a_{i+k}P(a_{i-1})$ If $a_{i-1} \neq a_i$ then we simply have $a_i > a_{i+k}$ which is a clear contradiction. Therefore $a_{i-1} = a_i$ , and even further all $a_j = a_i$ for $j < i$ . Note that $a_i = a_{i+k}$ and we can repeat the process for $a_{i+k}$ as it is a minimum. From this we can "induct" to prove that $a_n$ must be constant which clearly means it is non decreasing.

We now let $b_n \coloneq a_{n+1} - a_n$ and prove the following claim. Note that $b_n$ is nonnegative for all $n$ .

Claim: $b_n$ is bounded above

Assume FTSOC that $b_n$ is not bounded and achieves arbitrarily large values. Observe that $\begin{align*} P(a_n) = \prod_{i=1}^{k} a_{n+i} \\ = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right) > (a_n+b_n)^k\end{align*}$
Now since $b_n$ can achieve arbitrarily large values, we can select the index $n$ where $b_n > \frac{c_i}{{k \choose i}}$ for all $i$ and we have a clear contradiction.

Now there are obviously a finite amount of possibilities of $k$ -tuples $\left(b_n, b_{n+1}, \dots, b_{n+k-1}\right)$ where $n$ varies, but obviously an infinite amount of tuples that exist, so by PHP there exists a tuple that appears infinitely many times. This implies that $P(a_n) = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right)$ for infinitely many $a_n$ so we have $P(x) = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right)$ as a polynomial identity. Now, this immediately implies that all other $k$ -tuples appear only a finite amount of times, which also implies that eventually this special $k$ -tuple should be the only one that appears. This is only possible if $b_n = b_{n+1} = b_{n+2} = \dots = b_{n+k-1}$

We now finish by inducting down. FTSOC assume the index $i$ is the minimum value where $a_i$ "starts" behaving like an arithmetic sequence (Ex. $a_k = a_{k-1} + d$ for all $k \ge i+1$ ). Now we have $P(a_{i-1}) = \prod_{j = 1}^{k} \left(a_{i-1} + j \cdot d\right) = \prod_{j = 0}^{k-1} \left(a_{i} + j \cdot d\right)$ which directly implies $a_{i-1} + d = a_i$ , so we can just induct all the way down.

This post has been edited 1 time. Last edited by pi271828, Mar 29, 2024, 1:36 AM

Z K Y

The post below has been deleted. Click to close.

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

Pyramix

419 posts

Pyramix

#51 h Mar 30, 2024, 1:07 PM • 1 Y

Y by cubres

We prove that only arithmetic sequences work.

Suppose $a_1,a_2,\ldots$ is a sequence that works.

Claim 1: $P(x)$ is strictly increasing and injective polynomial for $x>0$ .
Proof. Take $a,b$ such that $a>b>0$ . Since $c_i$ are non-negative numbers, we have $c_ia^i \leq c_ib^i$ for each $1\leq i\leq k$ , and the inequality is strict for $i=k$ . Adding, we get that $P(a) > P(b)$ , as desired. $\blacksquare$

Since the polynomial is strictly increasing, it is naturally injective as well.

Claim 2: $a_{n+1}> a_n$ for each $n\in\mathbb{N}$ , or $a_n\equiv C'$ for each $n\in\mathbb{N}$ .
Proof. Suppose $a_{n+1} < a_n$ . Then, $P(a_{n+1}) < P(a_{n})\Longrightarrow \frac{a_{n+k+1}}{a_{n+1}}\cdot P(a_{n}) < P(a_{n})\Longrightarrow a_{n+k+1} < a_{n+1}$ Consider the minimum from $\{a_n,a_{n+1},\ldots,a_{n+k-1}\}$ . If $a_{n+t}$ is the minimum with $t\geq 1$ , then $a_{n+t+k} < a_{n+t}$ , which means minimum of $\{a_{n+k},a_{n+k+1},\ldots,a_{n+2k-1}\}$ is at most $a_{n+t}-1$ . Continuing, we get contradiction, unless $a_n=a_{n+1}=\cdots=a_{n+t}$ . Shifting $n$ front and back, we get that all terms are equal to some constant, $C'$ (which is the constant A.P.). $\blacksquare$

Claim 3: $a_{n+1}-a_{n}<C$ , for some constant $C$ .
Proof. Take $C$ such that for each $0\leq i < k$ , we have that $\binom{k}{i}C^{k-i} > c_i$ . Then, $(x+C)^k > P(x)$ for each $x>0$ . Finally, note
$(a_n+C)^k=P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}\geq a_{n+1}^k\Longrightarrow a_n+C\geq a_{n+1}\Longrightarrow a_{n+1}-a_n\leq C,$ as claimed. $\blacksquare$

Claim 4: $a_{n+1}-a_{n}$ is constant.
Proof. If $a_{n}=a_{n+1}$ for any $n$ then the sequence is constant, from Claim 2.
Assume that the sequence is not constant. Then, from Claim 2, it is strictly increasing, which means that it is unbounded above. So, it achieves infinitely many distinct positive integer values.
Note that $\{a_{n+1}-a_{n},a_{n+2}-a_{n+1},\ldots,a_{n+k+1}-a_{n+k}\}\subseteq\{1,2,\ldots,C\}$ . Since there are only finitely many subsets (at most $2^C-1$ ) possible, at least one subset appears infinitely many times for sufficiently many $n$ . Suppose that ordered tuple is $(a_{n+1}-a_{n},a_{n+2}-a_{n+1},\ldots,a_{n+k+1}-a_{n+k})=(b_1,b_2,\ldots,b_{k+1}).$ This means
$P(x)=\left(x+b_1\right)\left(x+b_1+b_2\right)\cdots\left(x+\sum_{i=1}^{k}b_i\right)$ for infintely many $x=a_n$ . Since $\deg P=k$ is finite, it means that the above equation is an identity.
Similarly,
$P(x)=\left(x+b_2\right)\left(x+b_2+b_3\right)\cdots\left(x+\sum_{i=2}^{k+1}b_i\right)$ is an identity.
Comparing, we get that $b_1=b_2$ by noticing that $P\left(-b_1\right)=P\left(-b_2\right)=0$ . Then, substituting $x+b_2$ as $x$ , we obtain $b_1=b_3$ and so on. Eventually, we get $b_1=b_2=\cdots=b_{k+1}$ . Hence, $a_{n+1}-a_{n}$ is constant, which means it is an increasing arithmetic sequences. Combining this with the fact that constant sequences work as well, we have that arithmetic sequences.

We now provide the construction for arithmetic sequences.

Suppose $a_n=a_1+(n-1)d$ for each $n\in\mathbb{N}$ . Then, the polynomial
$P(x)=(x+d)(x+2d)\cdots(x+kd)$ works, as $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ for each $n\in\mathbb{N}$ .

The proof is complete. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Qzxell

1 post

Qzxell

#52 h May 6, 2024, 10:12 PM • 1 Y

Y by cubres

799786 wrote:

For each integer $k\geq 2$ , determine all infinite sequences of positive integers $a_1$ , $a_2$ , $\ldots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0,$ where $c_0$ , $c_1$ , \dots, $c_{k-1}$ are non-negative integers, such that $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ for every integer $n\geq 1$ .

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8861 posts

HamstPan38825

#53 h Jun 23, 2024, 6:11 PM • 1 Y

Y by cubres

The answer is constant and increasing arithmetic sequences only, which work by setting $P(x) = (x+d)(x+2d) \cdots (x+kd)$ .

Claim. The sequence $\{a_n\}$ is nondecreasing.

Proof. Suppose that there is an index $i > N$ with $a_i > a_{i+1}$ . Notice that if $a > b > 0$ then $P(a) > P(b)$ as it has nonnegative coefficients. Thus, for any index $j$ , with $a_j > a_{j+1}$ , we have $a_{j+1}a_{j+2} \cdots a_{j+k} = P(a_j) > P(a_{j+1}) = a_{j+2}a_{j+3} \cdots a_{j+k+1}$ so in particular $a_j > a_{j+1} > a_{j+k+1}$ .

Then, for every index $i$ , either $a_i \geq a_{i-1}$ or $a_{i-1} < a_i$ , implying $a_i > a_{i+k}$ by the previous argument. Thus, there is a subsequence $a_{n_j}$ with $n_{j+1} \in \{n_j + k, n_j - 1\}$ such that $a_{n_{j+1}} \leq a_{n_j}$ for each $j$ .

Claim. $n_j > i$ for all $j > 1$ .

Proof. Note that $n_1 = i$ and $n_2 = i+k+1$ . Let $n_r$ be the first index less than $i$ . Then $n_{r-1} = n_r + 1 = i$ , otherwise we contradict minimality. But $a_i = a_{n_{r-1}} \leq a_{n_2} < a_i$ , contradiction. $\blacksquare$

In particular, I claim that there are infinitely many indices $j$ with $a_{n_{j+1}} < a_{n_j}$ . Suppose that for all $j > M$ equality holds; then we must have $n_{j+1} = n_j - 1$ for all these $j$ by assumption. Then for $A = n_M$ , notice that $n_{M+A-i} = A - (A-i) = i$ , contradiction.

Hence we have constructed an infinite sequence of strictly decreasing positive integers $a_{n_j}$ , which is a contradiction. $\blacksquare$

The rest of the proof goes rather quickly. By the previous claim, we will pick $a_n > M$ very large, with $M$ to be determined. Furthermore, let $b_i = a_i - a_{i-1} \geq 0$ for each $i$ .

Then, the given condition applied on $a_n$ yields that the polynomial
$Q(x) = P(x) - (x+b_{n+1})(x+b_{n+1}+b_{n+2}) \cdots (x+b_{n+1}+b_{n+2} + \cdots + b_{n+k})$ has a root at $a_n > 0$ .

Claim. $Q \equiv 0$ .

Proof. Suppose otherwise. Then there is an index $j$ with $c_{k-j} > S_j$ , where $S_j$ is the $j$ th symmetric sum of $b_{n+1}, b_{n+1}+b_{n+2}, \dots, b_{n+1}+b_{n+2}+\cdots+b_{n+k}$ . In particular, as all the $b_i$ are nonnegative integers, there are only finitely many possible values of the $k$ -tuple $(b_{n+1}, b_{n+2}, \dots, b_{n+k})$ as $c_{k-j}$ is a constant.

Let $i$ be the smallest index for which $c_{k-i} \neq S_i$ (the coefficients are not equal), and let $M_j = \sup |S_j - c_{k-j}|$ across all $k$ -tuples $(d_1, d_2, \dots, d_k)$ (note that $M_j$ only depends on the value of $c_{k-j}$ ) for each $j > i$ . It follows that
$\begin{align*} |Q(a_n) - P(a_n)| &= |c_{k-i}a_n^{k-i} - S_i a_n^{k-i} + c_{k-i-1}a_n^{k-i-1} - S_{i+1} a_n^{k-i-1} + \cdots + c_0 - S_k| \\ &\geq |c_{k-i}-S_i||a_n^{k-i}| - \sum_{j=i+1}^k |a_n^{k-j}| |S_j - c_{k-j}| \\ &\geq a_n^{k-i} - \sum_{j=i+1}^k M_j a_n^{k-j} \\ &\geq a_n^{k-i} - (k-i) \sup_j M_j a_n^{k-i-1}. \end{align*}$ By taking $a_n > M = (k-i) \sup_j M_j$ (which does not depend on $n$ ), we have a contradiction, as needed. $\blacksquare$

Hence the roots of $P$ are precisely $-b_{n+1}, -b_{n+1}-b_{n+2}, \cdots$ . In particular, repeating the argument for $a_{n+1} > a_n$ , we have
$\{b_{n+1}, b_{n+1}+b_{n+2}, \dots, b_{n+1}+\cdots+b_{n+k}\} = \{b_{n+2}, b_{n+2} + b_{n+3}, \dots, b_{n+2} + \cdots + b_{n+k+1}\}$ as all the elements in each set are distinct. But $b_{n+2}$ is less than all of the first element of the first set, so $b_{n+2} = b_{n+1}$ . Repeating this argument, we see that $b_n = d$ is constant for all $n > N$ .

To finish the problem, we just induct down. Given that $b_i = d$ for all $i \geq \ell+2$ , we have
$(a_\ell + d)(a_\ell + 2d) \cdots (a_\ell + kd) = P(a_\ell) = (a_\ell + b_{\ell+1})(a_\ell + b_{\ell+1} + d) \cdots (a_\ell + b_{\ell + 1} + (k-1)d).$ Considering this as a polynomial $R$ in $x = b_{\ell + 1} - d$ , we have $P(x) = P(0)$ and $P$ is strictly increasing on $(-a_\ell - d, \infty)$ , so $x = 0$ and $b_{\ell + 1} = d$ , as needed. This completes the induction and shows that $\{a_n\}$ is an arithmetic sequence, as needed.

This post has been edited 1 time. Last edited by HamstPan38825, Jun 23, 2024, 6:13 PM

Z K Y

The post below has been deleted. Click to close.

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

axolotlx7

133 posts

axolotlx7

#54 h Jul 30, 2024, 8:58 PM • 2 Y

Y by LLL2019, cubres

The answer is all arithmetic sequences with common difference $d \geq 0$ . The corresponding polynomial is $P(x)=(x+d)(x+2d) \dots (x+kd)$ .

Claim 1. $a_n \geq a_{n-1}$ for all $n$ .
Proof. Suppose FTSOC that $a_n < a_{n-1}$ for some $n$ . Then $a_{n+1}a_{n+2} \dots a_{n+k} = P(a_n) < P(a_{n-1}) = a_na_{n+1} \dots a_{n+k-1}$ implies $a_{n+k} < a_n$ , so consider the smallest index $n' \in [n+1, n+k]$ satisfying $a_{n'} < a_n$ . Then $a_{n'} < a_{n'-1}$ and we can repeat this process to generate a decreasing subsequence of positive integers, contradiction. $\square$

Claim 2. $(a_n)$ is either constant or strictly increasing.
Proof. Suppose $a_n = a_{n-1}$ . Then $a_{n+1}a_{n+2} \dots a_{n+k} = P(a_n) = P(a_{n-1}) = a_na_{n+1} \dots a_{n+k-1}$ implies $a_{n+k} = a_n$ , so by Claim 1 we have $a_n = a_{n+1} = \dots = a_{n+k}$ . The given condition implies $P(a_n) \geq a_n^k$ , and here equality holds which forces $P(x) = x^k$ . We can work backwards to obtain that $(a_n)$ is constant. $\square$

Henceforth suppose $(a_n)$ is strictly increasing.
Claim 3. $d_n = a_{n+1} - a_n$ is bounded.
Proof. Suppose not. Then consider
$a_n^k+c_{k-1}a_n^{k-1}+\dots + c_1a_n+c_0 = P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k} > a_{n+1}^k = (a_n + d_n)^k .$ However, for $d_n$ sufficiently large, each term in the expansion of the RHS will be larger than the corresponding term in the LHS, contradiction. $\square$

Let $S_n = (a_{n+1}-a_n, a_{n+2}-a_n, \dots, a_{n+k}-a_n)$ . As each element is bounded by applying Claim 3, there are only finitely possible values for $S_n$ . Hence by infinite Pigeonhole there exists $S = (z_1, z_2, \dots, z_k)$ such that $S_n = S$ infinitely often.

Claim 4. $P(x) = (x+z_1)(x+z_2) \dots (x+z_k)$ .
Proof. As $P(x)-(x+z_1)(x+z_2) \dots (x+z_k)$ is a polynomial and equals zero infinitely often, it must be identically zero. $\square$

Claim 5. $S_n = S$ for all sufficiently large $n$ .
Proof. Let $S_n = (w_1, w_2, \dots, w_k)$ . Then
$(a_n + z_1)(a_n + z_2) \dots (a_n + z_k) = P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k} = (a_n + w_1)(a_n + w_2) \dots (a_n + w_k)$ and as the $w_i$ 's are bounded, we can take $a_n > \max \{ w_1, \dots, w_k, z_1, \dots, z_k \}$ . Then if one expands each side, they are valid representations of the same number in base $a_n$ , so each corresponding term must be equal which implies $(x + z_1)(x + z_2) \dots (x + z_k) \equiv (x + w_1)(x + w_2) \dots (x + w_k)$ . As $w_1 < \dots < w_k$ and $z_1 < \dots < z_k$ , we conclude that $S_n = S$ as desired. $\square$

In particular, for sufficiently large $n$ we have $S_{n+1} = S_n$ , so $d_{n+1} = d_n$ , so $d_n$ eventually equals some constant $d$ . By Claim 4 we have $P(x)=(x+d)(x+2d) \dots (x+kd)$ and may work backwards to conclude that $d_n = d$ for all $n$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

N3bula

271 posts

N3bula

#55 h Oct 5, 2024, 3:42 AM • 1 Y

Y by cubres

Suppose the minimum of the sequence $a_n$ has the property $a_{n-1}>a_n$ for $n\neq 1$ , we get that $a_{n+k}P(a_{n-1})=a_nP(a_n)<a_nP(a_{n-1})$ which is a contradicition
as we know a minimum must exist. Thus $a_n$ is non strictly increasing. Note that there exists a value $y$ such that $(x+y)^k\geq P(x)$ for all $x$ . Thus we get
that $a_{n}+y\geq a_{n+1}$ from the non decreasing. This suffices to prove that it is bounded, from pigeon hole plus FTOA we get that is must be an arithmetic progression.

Z K Y

The post below has been deleted. Click to close.

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

Mathandski

757 posts

Mathandski

#56 h Jan 16, 2025, 6:55 PM • 1 Y

Y by cubres

Subjective Rating (MOHs)
Please contact westskigamer@gmail.com if there is an error with any of my solution for cash bounties by 3/18/2025.

Note on above: The beef is this solution is the same as Evan's so idt it's likely there'll be an error here

Attachments:

This post has been edited 1 time. Last edited by Mathandski, Jan 16, 2025, 6:58 PM

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

#57 h Feb 5, 2025, 7:20 AM • 1 Y

Y by cubres

Really nice problem but I could only do it for $k=2$ rip

The answer is $a_i=c+(i-1)d$ for every $i\geq 1$ where $c \in \mathbf N$ , $d \in \mathbf Z_{\geq 0}$ . This sequence clearly works (take $p=3d$ , $q=2d^2$ ). Now we will prove that this is the only sequence that works.

Claim: If $\{a_n\}$ is not constant then $a_{n+1}>a_n$ for every $n\geq 1$ .

Proof. Suppose that $a_2<a_1$ . Note that $a_1a_3>a_2a_3=a_1^2+pa_1+q>a_1^2 \ \Rightarrow \ a_3>a_1.$ Now suppose we have shown that $a_{2k+1}>a_{2k-1}>\dots>a_3>a_1>a_2>\dots>a_{2k-2}>a_{2k}$ for some $k\geq 1$ . Then, $\begin{align*} a_{2k+1}a_{2k+2}=a_{2k}^2+pa_{2k}+q<a_{2k-1}^2+pa_{2k-1}+q=a_{2k}a_{2k+1} & \ \Rightarrow \ a_{2k+2}<a_{2k} \\ a_{2k+1}^2\leq a_{2k+1}^2+pa_{2k+1}+q = a_{2k+2}a_{2k+3}<a_{2k+1}a_{2k+3} & \ \Rightarrow \ a_{2k+1}<a_{2k+3}. \end{align*}$ Thus, $a_{2k+3}>a_{2k+1}>a_{2k-1}>\dots>a_3>a_1>a_2>\dots>a_{2k-2}>a_{2k}>a_{2k+2}.$ By induction it follows that $\{a_{2n}\}$ is a strictly decreasing sequence. However this is a contradiction since $\{a_{2n}\}$ is a sequence of positive integers and as such, it cannot be strictly decreasing. Hence we must have $a_2\geq a_1$ . The same argument proves that $a_{i+1}\geq a_i$ for every $i\geq 1$ .

Suppose that $a_2=a_1$ . Then, $a_3=\frac{a_1^2+pa_1+q}{a_1}$ and $a_4=\frac{a_2^2+pa_2+q}{a_3}=\frac{a_1^2+pa_1+q}{\frac{a_1^2+pa_1+q}{a_1}}=a_1.$ But we have proved already that $a_4\geq a_3$ i.e. $a_1\geq \frac{a_1^2+pa_1+q}{a_1} \ \Rightarrow \ 0\geq pa_1+q \ \Rightarrow \ p=q=0.$ Thus, $a_i^2=a_{i+1}a_{i+2}$ for every $i\geq 1$ . From this we derive that $a_i$ must be constant. The claim follows. ////

Let us define another sequence of positive integers $\{t_n\}_{n\geq 2}$ by $a_{n+1}=a_n+t_{n+1}$ . So we have $\begin{align*} a_i^2+pa_i+q & =(a_i+t_{i+1})(a_i+t_{i+1}+t_{i+2}) \\ pa_i+q & =a_i(2t_{i+1}+t_{i+2})+t_{i+1}(t_{i+1}+t_{i+2}) \qquad (1)\end{align*}$
Let $l$ be such that $a_l>q$ . Note that, from $(1)$ , we have $q>a_l(2t_{l+1}+t_{l+2}-p)>q(2t_{l+1}+t_{l+2}-p) \ \Rightarrow \ 2t_{l+1}+t_{l+2}-p\leq 0.$ Thus we must have $2t_{n+1}+t_{n+2}\leq p\qquad (2)$ for every $n\geq l$ . Let $S$ be the set of all $n\in \mathbf N$ such that if $n\in S$ then $2t_{n+1}+t_{n+2}<p$ . Let $p':=\max_{n\in S}(2t_{n+1}+t_{n+2})<p$ . Suppose that $S$ has infinitely many elements. For every $n\in S$ , $\begin{align*} a_n(p-p')\leq a_n(p-2t_{n+1}-t_{n+2})=t_{n+1}(t_{n+1}+t_{n+2})-q \\ \Rightarrow \ a_n\leq \frac{t_{n+1}(t_{n+1}+t_{n+2})-q}{p-p'}\end{align*}$ Note that $t_{n+1}(t_{n+1}+t_{n+2})$ is bounded (this is quite clear from $(2)$ ). It follows that $a_n$ is bounded for every $n\in S$ , but this is a contradiction since we showed that $\{a_n\}$ is strictly increasing. Thus $S$ must be a finite set. And so there must exist some $m\geq l$ such that $2t_{n+1}+t_{n+2}=p$ for every $n\geq m$ and also from $(1)$ , $t_{n+1}(t_{n+1}+t_{n+2})=q$ . From these equations it's easy to get that $t_{n+1}$ must be constant for every $n\geq m$ .

Let $t_i=t$ for $i\geq m+1$ then we also have $p=3t$ , $q=2t^2$ . Now the equation in $(1)$ for $i=m-1$ implies that $3ta_{m-1}+2t^2=a_{m-1}(2t_m+t)+t_m(t_m+t)\iff (t_m-t)(2a_{m-1}+3t_m+t)=0,$ thus $t_m=t$ . At this point it is evident by induction that we must have $t_i=t$ for every $i\geq 2$ . 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.

ihatemath123

3446 posts

ihatemath123

#58 h Feb 22, 2025, 4:16 PM • 1 Y

Y by cubres

Arithmetic sequences clearly work, so we will show they are the only solutions.

Claim: If $a_i$ is not constant, it is strictly increasing.
Proof: Suppose for the sake of contradiction that $a_1 > a_2$ (we can truncate a sequence so that this is true). Then, since $P$ is an increasing function, we have
$a_2 a_3 \cdots a_{1+k} > a_3 a_4 \cdots a_{2+k} \implies a_2 > a_{2+k},$ so there exists an integer $i$ strictly between $1$ and $2+k$ for which $a_i > a_{i+1}$ and $a_{i+1} < a_2$ . Now we can truncate our sequence at $i$ and repeat until we get a contradiction.

Claim: $a_{i+1} - a_i$ is bounded.
Proof: For a sufficiently large constant $C$ , we have $(x+C)^k > P(x)$ for all $x$ , so $a_{i+1} < a_i + C$ .

So by pigeonhole, the function $f(i) = (a_{i+1} - a_i, a_{i+2} - a_i, \dots, a_{i+k} - a_i)$ must map infinitely many integers $i$ to the same $k$ -tuple $(r_1, r_2, \dots, r_k)$ . In other words, $P(x) = (x-r_1) \cdots (x-r_k)$ for infinitely many $x$ , implying that the equality holds for all $x$ . So, $f(i)$ is a constant function. Comparing $f(i)$ and $f(i+1)$ , it follows that $a_1, a_2, \dots$ is an arithmetic sequence.

This post has been edited 1 time. Last edited by ihatemath123, Feb 22, 2025, 4:38 PM

Z K Y