conditional sequence

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

19 users

TOPICS

No tags match your search

M

No tags match your search

M

conditional sequence

G H J

Reveal topic tags

modular arithmetic

least common multiple

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: USAMO 1995

The post below has been deleted. Click to close.

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

MithsApprentice

2390 posts

MithsApprentice

#1 h Oct 23, 2005, 12:25 AM • 4 Y

Y by Adventure10, Rounak_iitr, Mango247, cubres

Suppose $\, q_{0}, \, q_{1}, \, q_{2}, \ldots \; \,$ is an infinite sequence of integers satisfying the following two conditions:

(i) $\, m-n \,$ divides $\, q_{m}-q_{n}\,$ for $\, m > n \geq 0,$
(ii) there is a polynomial $\, P \,$ such that $\, |q_{n}| < P(n) \,$ for all $\, n$

Prove that there is a polynomial $\, Q \,$ such that $\, q_{n}= Q(n) \,$ for all $\, n$ .

Z K Y

The post below has been deleted. Click to close.

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

77 posts

#2 h Aug 2, 2010, 4:11 AM • 15 Y

Y by Mediocrity, SidVicious, deimis1231, HolyMath, anantmudgal09, mijail, Lcz, Adventure10, Mango247, Tastymooncake2, MS_asdfgzxcvb, and 4 other users

Step 1: Suppose $P$ has degree $d$ . Let $Q$ be the polynomial of degree at most $d$ with $Q(x)=q_x$ for $0\leq x\leq d$ . Since the $q_x$ are all integers, $Q$ has rational coefficients, and there exists $k$ so that $kQ$ has integer coefficients. Then $m-n|kQ(m)-kQ(n)$ for all $m,n\in \mathbb N_0$ .

Step 2 We show that $Q$ is the desired polynomial.

Let $x>n$ be given. Now
$kq_x\equiv kq_m\pmod{x-m}\text{ for all integers }m\in[0,d]$
Since $kQ(x)$ satisfies these relations as well, and $kq_m=kQ(m)$ ,
$kq_x\equiv kQ(x)\pmod{x-m}\text{ for all integers }m\in[0,d]$
and hence
$kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1)$
Now
$\begin{align*} \text{lcm}(x,x-1,\ldots, x-i-1)&=\text{lcm}[\text{lcm}(x,x-1,\ldots, x-i),x-i-1]\\ &=\frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[\text{lcm}(x,x-1,\ldots, x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[x(x-1)\cdots(x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{(i+1)!} \end{align*}$
so by induction $\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}$ . Since $P(x), Q(x)$ have degree $d$ , for large enough $x$ (say $x>L$ ) we have $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$ . By (1) $kq_x$ must differ by a multiple of $\text{lcm}(x,x-1,\ldots, x-d)$ from $kQ(x)$ ; hence $q_x$ must differ by a multiple of $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ from $Q(x)$ , and for $x>L$ we must have $q_x=Q(x)$ .

Now for any $y$ we have $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ for any $x>L$ . Since $x-y$ can be arbitrarily large, we must have $Q(y)=q_y$ , as needed.

Z K Y

The post below has been deleted. Click to close.

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

69 posts

#3 h Sep 17, 2013, 3:13 PM • 2 Y

Y by Adventure10, Mango247

Does anyone have a shorter solution?

Z K Y

The post below has been deleted. Click to close.

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

1980 posts

#4 h Aug 17, 2016, 6:12 PM • 4 Y

Y by Wizard_32, Aryan-23, Adventure10, Mango247

Nice!

We consider the polynomial $f$ of the minimal degree such that $a_n \le f(n)$ for all but finitely many $n$ . Let $d$ be the degree of $f$ . We consider a polynomial $g$ of degree $d$ such that $g(i)=a_i$ for $1 \le i \le d+1$ . By the Lagrange Interpolation formula, this polynomial is of rational coefficients and uniquely defined. Let $N>0$ be a constant such that $h(x)=Ng(x)$ is a polynomial with integer coefficients. We replace the sequence $a_n$ by $b_n=Na_n$ . This does not affect our divisibility relation and the other conditions are scaled accordingly. Choose $m$ sufficiently large, in particular $m>c$ where $c>0$ is a constant we shall disclose later in the proof. Now, we have $\begin{align*} m-i \mid (b_m-b_i)-(h(m)-h(i)) = (b_m-h(m)) \end{align*}$ where $1 \le i \le d+1$ . Therefore, we have the relation: $\begin{align*} \operatorname{lcm}(m-1,\dots, m-d, m-d-1) \mid |b_m-h(m)| \end{align*}$ and we observe that $|b_m-h(m)|_{m \ge 1}$ is bounded above by a polynomial of degree $d$ , i.e., there exists a constant $a>0$ such that $|b_m-h(m)| \le am^d$ . However, we see that the relation $\begin{align*} x_1\cdot \dots \cdot x_k \mid \operatorname{lcm}(x_1,\dots, x_k)\cdot \Pi \gcd (x_i,x_j) \end{align*}$ holds for all integers $x_1,\dots, x_k$ , where in the last product the gcd is taken over all pairs $1 \le i < j \le k$ . This result is established by comparing the $v_p$ 's on each side. Now, this directly translates into an inequality $A \le B$ if $A \mid B$ . Notice that $\gcd (a,b) \le |a-b|$ . Therefore, we have $\begin{align*} am^d \ge \operatorname{lcm}(m-1,...,m-d-1) \ge \frac{(m-1)\cdot \dots \cdot (m-d-1)}{\Pi_{1 \le i<j \le d+1} \gcd(m-i,m-j)} \ge \frac{(m-1)\cdot \dots \cdot (m-d-1)}{\Pi_{1 \le i < j \le d+1} (j-i)}=O(m^{d+1}), \end{align*}$ yielding a contradiction for all sufficiently large $m$ , unless $b_m=h(m)$ . We deduce that $b_m=h(m)$ for all sufficiently large $m$ , i.e., for all $m>M$ for some constant $M>0$ . Now, we take $n \le M$ and notice that $m-n \mid b_m-b_n$ implies that $m-n \mid |b_n-h(n)|$ which further yields, due to the size of $m$ , that $b_n=h(n)$ .

In summary, we conclude from the above deductions that $b_n=h(n)$ for all $n \in \mathbb{N}$ and so, $a_n=g(n)$ for all $n \in \mathbb{N}$ . The result follows.

Comment The result is sharp, namely, we cannot reduce it to showing that $g \in \mathbb{Z}[X]$ . A counter example can be the sequence $a_n=\binom{n}{2}+2016$ which clearly, satisfies all our conditions but is not in $\mathbb{Z}[X]$ .

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#5 h Oct 3, 2018, 4:13 AM • 1 Y

Y by Adventure10

Let $d=\deg P$ . Let $Q(x)$ be the unique polynomial with degree at most $d$ such that $Q(x)=q_x$ for all $0\le x\le d$ . It exists because we can set up a system of $d+1$ variables and linear equations, and the solution exists and is unique because the Vandermonde determinant is nonzero. This also shows that $H$ has rational coefficients. Pick $k\in\mathbb{Z}$ such that $H=kQ\in\mathbb{Z}[x]$ , and let $a_n=kq_n$ . It now suffices to show that $a_n=H(n)$ for all $n\ge 0$ , where we know that $H(n)=n$ for all $0\le n\le d$ , $\deg H\le d$ , and $m-n\mid a_m-a_n$ for all $m\not=n$ .

Suppose $n\ge d+1$ . Then, we have that
$\begin{align*} a_n &\equiv a_0 = H(0)\pmod{n} \\ a_n &\equiv a_1 = H(1)\pmod{n-1} \\ &\vdots \\ a_n &\equiv a_d = H(d) \pmod{n-d}. \end{align*}$ By the Chinese Remainder Theorem, this has a unique solution $\pmod{f(n)}$ where $f(n):=\mathrm{lcm}(n-d,n-d+1,\ldots,n-1,n)$ . Note that one solution that definitely works is $H(n)$ since $H\in\mathbb{Z}[x]$ . Thus, $a_n\equiv H(n)\pmod{f(n)}$ . The key point is that $n^{d+1}/f(n)$ is bounded above by some constant that only depends on $n$ (I think something like $d\cdot (d-1)^2\cdots 2^{d-1}$ works), so in particular, $f(n)$ grows faster than $P(n)$ . Eventually then, we must have $f(n)>100k P(n)$ , and since $|a_n|<k P(n)$ and $a_n\equiv H(n)\pmod{f(n)}$ , we see that $a_n=H(n)$ for sufficiently large $n$ . So $a_n=H(n)$ for all $n\ge N$ .

It remains to show that $a_n=H(n)$ for all $n<N$ . We see that $a_n\equiv a_m=H(m)\equiv H(n)\pmod{m-n}$ for all $m\ge N$ , so by taking $m$ to be sufficiently large, we learn that $a_n=H(n)$ , as desired. Dividing by $k$ , we get that $q_n=Q(n)$ for all $n$ .

This post has been edited 1 time. Last edited by yayups, Oct 3, 2018, 5:12 PM

Z K Y

The post below has been deleted. Click to close.

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

616 posts

#6 h May 19, 2020, 7:00 AM • 2 Y

Y by Superguy, rafayaashary1

For those interested, here is a massive generalization (posted today!)

Z K Y

The post below has been deleted. Click to close.

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

1741 posts

#7 h Aug 29, 2020, 11:49 PM • 5 Y

Y by Mathematicsislovely, MatBoy-123, JG666, hakN, Rounak_iitr

Let $d$ be the degree of $P$ , and let $Q$ be the (unique) rational polynomial with $Q(i)=q_i$ for $i=0,\ldots,d$ . Appropriately scale up everything so that $Q$ has integer coefficients.

Lemma: For all $d$ , $\operatorname{lcm}(n,n-1,\ldots,n-d)=O\big(n^{d+1}\big).$
Proof. Evidently $\operatorname{lcm}(n,n-1,\ldots,n-d)\le n(n-1)\cdots(n-d)=O\big(n^{d+1}\big)$ . The lower bound can be attained easily via basically any bound; for instance, $\operatorname{lcm}(n,\ldots,n-d)\ge\frac{n(n-1)\cdots(n-d)}{\prod_{i<j}\gcd(n-i,n-j)}\ge\frac{n(n-1)\cdots(n-d)}{\prod_{i<j}(j-i)}=O\big(n^{d+1}\big).$ $\blacksquare$

Claim: For sufficiently large $n$ , we have $q_n=Q(n)$ .

Proof. We must have $q_n\equiv q_i=Q(i)\equiv Q(n)\pmod{n-i}$ for $i=0,\ldots,d$ , so $q_n\equiv Q(n)\pmod{\operatorname{lcm}(n,\ldots,n-d)}.$ If $q_n\ne Q(n)$ , then for some nonzero $k$ we have $q_n=Q(n)+k\operatorname{lcm}(n,\ldots,n-d)=O\big(n^{d+1}\big)$ , which will exceed $P(n)$ in absolute value for sufficiently large $n$ . $\blacksquare$

To finish the proof, observe that for every $m$ , we have $q_m\equiv q_n=Q(n)\equiv Q(m)\pmod{n-m}$ for sufficiently large $n$ . By taking $n$ large, $q_m=Q(m)$ , as needed.

Z K Y

The post below has been deleted. Click to close.

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

GeronimoStilton

1520 posts

GeronimoStilton

#8 h Nov 4, 2020, 3:57 AM

Y by

Let $P$ have degree $k$ . Let the polynomial $Q$ of minimal degree such that $Q(i)=q_i$ for each $0\le i\le k$ be $Q^*$ . Note that $Q^*$ is a rational polynomial with degree at most $k$ . Let $d\in\mathbb{Z}_{>0}$ be minimal with $dQ^*\in\mathbb{Z}[x]$ . Define $p_i=dq_i$ for each $i$ and note the $p_i$ satisfy the same properties as the $q_i$ by considering $P'=dP(n)$ , and moreover the minimal polynomial of $p_0,\dots,p_k$ is an integer polynomial $\tilde{Q}$ . Now, consider $n>k$ . Observe that we must have $\tilde{Q}(n)\equiv p_n\pmod{n-i}$ for each $0\le i\le k$ because of the condition and the fact that $\tilde{Q}$ is an integer polynomial. Note that any $n-i,n-j$ have common divisor dividing $k!$ , hence we can write
$n\cdot \binom{n}{k} \mid \tilde{Q}(n)-p_n.$ For large values of $n$ , $|\tilde{Q}(n)+ an\cdot \binom{n}{k}|>10|P(n)|$ for all $a\ne0$ so $p_n=\tilde{Q}(n)$ . Now, use large $n$ to uniquely determine every value of $p_i$ for which the previous argument does not work, and note that $p_i=\tilde{Q}(i)$ is the only feasible solution $p_i$ to the modular equations we get. Hence, $q_n=Q^*(n)$ for each $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.

694 posts

#9 h Dec 14, 2020, 5:44 AM

Y by

MithsApprentice wrote:

Suppose $\, q_{0}, \, q_{1}, \, q_{2}, \ldots \; \,$ is an infinite sequence of integers satisfying the following two conditions:

(i) $\, m-n \,$ divides $\, q_{m}-q_{n}\,$ for $\, m > n \geq 0,$
(ii) there is a polynomial $\, P \,$ such that $\, |q_{n}| < P(n) \,$ for all $\, n$

Prove that there is a polynomial $\, Q \,$ such that $\, q_{n}= Q(n) \,$ for all $\, n$ .

Suppose $\text{deg} \ P = d$ . Then let by Lagrange Interpolation formula, there exists $Q \in \mathbb{Q}[x]$ of degree $d$ such that $Q(i) = q_i$ for $0 \le i \le d$ . For now, we alter $q_i \to kq_i$ , $P \to kP = P'$ and $Q \to kQ = Q'$ such that $Q' \in \mathbb{Z}[x]$ , and the problem is still true.

We wll know prove that $Q'$ satisfies the requirement of the problem.
Fix an integer $\ell > d$ . Notice that we have
$\ell - i \mid kq_{\ell} - kq_i, \ \forall 0 \le i \le d$ and since $Q'(i) = kq_i$ for $0 \le i \le d$ , we have $\ell - i \mid kq_{\ell} - Q'(i)$ . But since $Q' \in \mathbb{Z}[x]$ , we have $\ell - i \mid Q'(\ell) - Q'(i)$ , which forces
$\ell - i \mid kq_{\ell} - Q'(\ell) \ \text{for } 0 \le i \le d$ This forces
$\text{lcm} ( \ell, \ell - 1, \dots, \ell - d) \mid kq_{\ell} - Q'(\ell)$ Claim. $\text{lcm}(\ell, \ell - 1, \dots, \ell - d) = O(\ell^{d + 1})$ .
Proof. We know that $\text{lcm}(\ell, \ell - 1, \dots, \ell - d) \le \ell(\ell - 1) \dots (\ell - d) = O(\ell^{d + 1})$ , and the lower bound is attained by
$\text{lcm}(\ell, \dots, \ell - d) \ge \frac{\ell(\ell - 1)\dots (\ell - d)}{\prod_{i < j} \gcd(\ell - i, \ell - j)} \ge \frac{\ell(\ell - 1) \dots (\ell - d)}{\prod_{i <j} \gcd(i,j)} = O(\ell^{d + 1})$

Claim. $Q'(n) = kq_n$ for all sufficiently large integer $n$ .
Proof. From the condition of the problem, we have $|kq_n| < P'(n)$ for all $n \in \mathbb{N}$ .
So, $kq_{\ell} - Q'(\ell) \le |Q'(\ell)| + |P'(\ell)|$ , and therefore for sufficiently large $n$ , if $Q'(n) \not= kq_n$ , we must have
$n(n - 1) \dots (n - d) \le |kq_n - Q'(n)| \le |P'(n)| + |Q'(n)|$ which is a contradiction as $P' + Q'$ is of degree $d$ .

Claim. $Q'(n) = kq_n$ for all positive integers $n$ .
Proof. Suppose there exists a positive integer $\ell$ such that $Q'(\ell) \not= kq_{\ell}$ . We have
$n - {\ell} \mid Q'(n) - Q'(\ell) \ \text{and} \ n - \ell \mid kq_n - kq_{\ell}$ for all sufficiently large $n$ . Since $kq_n = Q'(n)$ for all sufficiently large $n$ , then we must have
$n - {\ell} \mid Q'(\ell) - kq_{\ell}$ for all sufficiently large $n$ . However, this is a contradiction, as we can take $n - \ell > |Q'(\ell) - kq_{\ell}| + 10^{100}$ , and we are done.

To conclude, we have $kQ(n) = Q'(n) = kq_n$ , which forces $Q(n) = q_n$ for all $n \in \mathbb{N}$ .

This post has been edited 1 time. Last edited by IndoMathXdZ, Dec 14, 2020, 5:45 AM

Z K Y

The post below has been deleted. Click to close.

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

283 posts

#10 h Mar 16, 2023, 8:23 PM • 1 Y

Y by mulberrykid

Let $P(x)$ have degree $k$ . Suppose that $Q(x)$ is the polynomial of degree $k$ such that $Q(x)=q_x$ for $1\leq{}x\leq{}k$ . We now claim that if we fix the first $k$ terms of the sequence $q_i$ such that it satisfies the conditions, the rest of the sequence is fixed. (If it is fixed, it also must be equivalent to the polynomial $Q(x)$ , since $Q(x)$ satisfies the conditions).

Notice that $Q$ must be a polynomial with rational coefficients (comes from finite differences), therefore there is an integer $c$ such that $cQ$ is a polynomial with integer coefficients. For some very large $x>n$ , we find that
$\text{lcm}{}(x,x-1,\dots{},x-k)\geq{}\frac{x(x-1)\dots{}(x-k)}{ck!(k-1)!\dots{}1!}$ and by bounding on $q_x$ (Since by the second condition, we must have that $|q_x|<P(x)$ ), we find that we must have $Q(x)=q_x$ for all $x$ , and 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.

8902 posts

#11 h Nov 27, 2023, 7:33 AM • 1 Y

Y by Rounak_iitr

The hardest part of the problem is really getting started.

Fix $\deg Q = d = \deg P$ , and let $Q$ be the polynomial with degree $d$ that agrees with $q_i$ for $0 \leq i \leq d$ . We can assume that $Q$ is an integer polynomial; otherwise just transform $Q \to kQ$ where $kQ \in \mathbb Z[X]$ and show that $kQ(n) = kq_n$ for every $n$ .

Now, for any $n \geq d$ , note that $q_n \equiv Q(n) \pmod {\operatorname{lcm}(n, n-1, \dots, n-d)}.$ Call this $A_n$ .

Claim. $A_n = O(n^{d+1})$ .

Proof. Intuitively, this is because for large $n$ , the numbers ``don't share many common factors." More rigorously, $A_n > \frac{n(n-1)\dots(n-d)}{\prod_{i<j} \gcd(i, j)} = O(n^{d+1}). \ \blacksquare$
To finish, pick very large $n$ and suppose that $q_n \neq Q(n)$ ; then it follows that $|q_n - Q(n)| > A_n$ . But by the claim this implies $|q_n| > P(n)$ , contradiction! Thus, $q_n$ and $Q(n)$ agree at infinitely many values, and $Q(n) = q_n$ for all $n$ .

This post has been edited 1 time. Last edited by HamstPan38825, Dec 2, 2023, 7:44 PM

Z K Y

The post below has been deleted. Click to close.

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

199 posts

#12 h Feb 7, 2024, 5:32 PM

Y by

Let $N$ be a sufficiently large integer and let $Q$ be the interpolation polynomial of the points $(0, q_0), (1, q_1), \dots, (N, q_N)$ . We'll show that $Q$ is the desired polynomial. We can assume that $Q$ is an integer polynomial; otherwise just transform $Q \to kQ$ where $kQ \in \mathbb Z[X]$ and show that $kQ(n) = kq_n$ for every $n$ . We'll do it by induction. Base case is clear. For induction step, assume $Q(n) \neq q_n$ for some $n$ . Since $q_n \equiv q_i = Q(i) \equiv Q(n) (n - i)$ , so $\text{lcm}(1, 2, \dots, n-1) \mid q_n - Q(n)$ . Therefore there exists $k$ such that $q_n = Q(n) + \text{lcm}(1, 2, \dots, n-1)k$ . Now consider the following claim:

Claim: $\text{lcm}(1, 2, \dots, n)$ grows faster than any polynomial.

Proof. Assume not. Then there exists $k$ such that $n^k > \text{lcm}(1, 2, \dots n)$ for all sufficiently large integer $n$ . But we have $\text{lcm}(1, 2, \dots, n) > \prod_{p \le n} p^{\log_p(n) - 1} = \prod_{p \le n} \frac{n}{p} = \frac{n^{\pi(n)}}{p_1p_2\cdots p_{\pi(n)}} > \frac{n^{k+1}}{p_1p_2\cdots p_{k+1}}$ , hence we get $n^k > \frac{n^{k+1}}{p_1p_2\cdots p_{k+1}}$ for all sufficiently large $n$ , a contradiction. $\blacksquare$

Note that $|Q(i)| < P(i)$ for all $0 \le i \le N$ , so $\deg Q \le \deg P$ . Thus $q_n$ has to be equal to $Q(n)$ , otherwise we get $\text{lcm}(1, 2, \dots, n)$ is bounded by some polynomial, contradicting the claim. Hence the induction step is proved. $\blacksquare$

Remark. In fact, we have $\text{lcm}(1, 2, \dots, n) = n \cdot \text{lcm}(\binom{n-1}{0}, \binom{n-1}{1}, \dots, \binom{n-1}{n-1}) \ge \binom{n-1}{0} + \binom{n-1}{1} + \dots + \binom{n-1}{n-1} = 2^{n-1}$ , which immediately implies the claim.

This post has been edited 2 times. Last edited by thdnder, Feb 9, 2024, 4:41 PM

Z K Y

The post below has been deleted. Click to close.

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

419 posts

#13 h Mar 26, 2024, 7:17 AM

Y by

The main idea of this problem is the following lemma:

Lemma. For all non-negative integers $d$ , we have
$\text{lcm}(n,n-1,\ldots,n-d)=O(n^{d+1})$ Proof. For the upper bound, simply note that
$\text{lcm}(n,n-1,\ldots,n-d)\leq n(n-1)\cdots(n-d)=O(n^{d+1}),$ while for the lower bound, we use the fact that for $1\leq i < j\leq d$ , we have $\gcd(n-i, n-j)\leq j-i$ , which means
$\text{lcm}(n,n-1,\ldots,n-d)\geq \frac{n(n-1)\cdots(n-d)}{\prod_{1\leq i < j\leq n}(j-i)}=O(n^{d+1}),$ so the lemma is true. $\blacksquare$

Let $d$ be the degree of $P$ . So, $q_n=o(P(n))=o(n^d)$ for sufficiently large $n$ .
By Lagrange Interpolation, there exists a unique rational polynomial $R$ of degree at most $d$ such that $R(i)=q_i$ for each $0\leq i\leq d$ .

Claim: $R(n)=q_n$ for all sufficiently large $n$ .
Proof. Note that we have
$q_n\equiv q_i\equiv R(i)\equiv R(n)\pmod{n-i}$ for each $0\leq i\leq d$ . Hence, we have
$q_n\equiv R(n)\pmod{\text{lcm}(n-1,n-2,\ldots,n-d)}\Longrightarrow q_n=k\ \text{lcm}(n-1,n-2,\ldots,n-d)+R(n)$ So, if $k\neq0$ , then $q_n=O(n^{d+1})$ . But we also have $q_n=o(n^d)$ for sufficiently large $n$ . This means $O(n^{d+1})=o(n^d)$ , which is absurd. Hence, $k=0$ is forced for large $n$ , which means $q_n=R(n)$ , as desired. $\blacksquare$

Finish:
Note that for any $m$ and sufficiently large $n$ , we have that
$q_m\equiv q_n\equiv R(n)\equiv R(m)\pmod{n-m}$ So, $n-m\mid q_m-R(m)$ for all sufficiently large $n$ , which forces $q_m=R(m)$ .

So, $R$ is the required construction for $Q$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

5685 posts

#14 h Apr 29, 2024, 7:18 PM

Y by

First we clearly see that $P$ must have positive leading coefficient as it is positive for all $n$ .

Consider the polynomial constructed by Lagrange Interpolation with rational coefficients and degree the same as that of $P$ so that $i$ maps to $q_i$ for all $i \in \{0, 1, \ldots, d\}$ and $N$ be a positive integer satisfying that this polynomial times $N$ has integer coefficients. Let $R(x)$ be this polynomial with integer coefficients. Additionally, let $x_i = N q_i$ for each $i$ . It suffices to show there exists a polynomial $S$ with $S(n) = x_n$ for all $n$ . Clearly $m - n \mid x_m - x_n$ for all $m,n$ . WLOG that $R(x)$ has a nonnegative leading coefficient (since we can switch $x_i$ with $- x_i$ and all the conditions stay the same).

We see that $R(i) = x_i \forall i\in \{0,1, \ldots,d\}$ .

Claim: For all sufficiently large positive integers $n$ , we have $R(n) = x_n$ .
Proof: Suppose otherwise for some large $n$ . We have $n - i \mid x_n - x_i$ for any $0 \le i \le d$ , so $x_n \equiv R(i) \pmod{n-i}$ .

Hence $x_n \equiv R(n) \pmod{n-i}$ , so $x_n \equiv R(n) \pmod{\mathrm{lcm}(n-d, n-(d-1), \ldots, n)}$ Now, we see that $\mathrm{lcm}(n-d, n-(d-1), \ldots, n) \ge \frac{\prod_{i=0}^d (n - (d - i)) }{\prod_{n-d \le i < j \le n}\gcd(i,j) } \ge \frac{\prod_{i=0}^d (n - (d - i)) }{\prod_{n-d \le i < j \le n} (j-i)} \ge \frac{\prod_{i=0}^d (n - (d - i)) }{d^{d^2}}$ The RHS is a polynomial with degree $d + 1$ and positive leading coefficient, so for sufficiently large $n$ , it exceeds $N P(n) + R(n) + 1434$ .

Suppose that $x_n \ne R(n)$ for some sufficiently large $n$ . Then $|x_n|$ is at least $|R(n) - \mathrm{lcm}(n-d,n-(d-1), \ldots, n)|$ . As $n$ is large, $\mathrm{lcm}(n-d, n-(d-1),\ldots, n)$ exceeds $N P(n) + R(n) + 1434$ , so $|x_n| \ge N P(n) + 1434 > N P(n)$ , which is a contradiction since $|x_n|= N |q_n| < N P(n)$ . $\square$

Let $r$ be any positive integer and $m$ be any positive integer with $q_m = R(m)$ . We have $m - r \mid R(m) - x_r$ , however, we also have $m - r \mid R(m) - R(r)$ , so $m - r \mid (R(m) - R(r)) - (R(m) - x_r) = x_r - R(r),$ so taking $m$ sufficiently large gives that $x_r = R(r)$ , so we can just set $S(x) = R(x)$ (in particular $Q(x) = \frac{R(x)}{N}$ ).

This post has been edited 1 time. Last edited by megarnie, Apr 29, 2024, 7:18 PM

Z K Y

The post below has been deleted. Click to close.

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

314 posts

N3bula

#15 h Sep 21, 2024, 10:31 AM

Y by

Let $Q(x)$ be the polynomial such that $Q(0)=q_0$ , $Q(1)=q_1$ , \dots, $Q(d)=q_d$ where $d$ is the degree of $P(n)$ , note that for all $n$ we have $q_n\equiv Q(n) \pmod{\text{lcm}(n(n-1)(n-2)\dots(n-d))}$ ,
thus by taking large enough $n$ and using the fact that $\text{lcm}(n(n-1)(n-2)\dots(n-d))\geq \frac{n(n-1)(n-2)\dots(n-d)}{1!\cdot 2!\cdot 3!\dots d!}$ we get that for all large enough $n$ that $q_n=Q(n)$
and thus from the bound on small $n$ we can also get that for all $n$ $Q(n)=q_n$ .

Z K Y

The post below has been deleted. Click to close.

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

147 posts

#16 h Mar 31, 2025, 6:48 AM

Y by

Let the degree of $P$ be $d$ , and let $Q(x)$ be the unique polynomial of degree $d$ such that $Q(i)=q_i$ for $i=0,1,2,\dots ,d$ , and assume it has integer coefficients by scaling.

Lemma: For integers $d$ , we get that $\operatorname{lcm}(n,n-1,n-2,\dots n-d)=\Theta(n^{d+1})$ Proof of lemma: We have that $\operatorname{lcm}(n,n-1,n-2,\dots n-d)\le n(n-1)(n-2)\dots (n-d)=O(n^{d+1})$ . To see the lower bound, we get that
$\begin{align*} \operatorname{lcm}(n,n-1,n-2,\dots n-d) &\ge \frac{n(n-1)(n-2)(n-3)\dots (n-d)}{\Pi_{i<j} \gcd(n-i,n-j)}\\ &\ge \frac{n(n-1)(n-2)(n-3)\dots (n-d)}{\Pi_{i<j} (i-j)}\\ &=\Omega(n^{d+1}) \end{align*}$ Combining the two bounds, we get the desired lemma $\square$ .

I use this lemma to show the result for sufficiently large $n$ and then interpolate it to all integers $n$ .

Claim: For sufficiently large integers $n$ , we get that $q_n=Q(n)$
Proof of claim: We have that $q_n\equiv q_i\equiv Q(i)\equiv Q(n) \pmod{n-i}$ for $i$ in $0,1,2,\dots, d$ and thus $q_n\equiv Q(n) \pmod{\operatorname{lcm}(n,n-1,n-2,\dots,n-d)}$ so this gives us the desired claim due to the previous lemma noting that $P$ is a polynomial of degree $d$ . $\square$

Now to finish, we want to show $q_m=Q(m)$ for all integers $m$ . For this, notice that $q_m\equiv q_n=Q(n)\equiv Q(m)\pmod{n-m}$ for sufficiently large $n$ , which finishes. $\blacksquare$

This post has been edited 2 times. Last edited by quantam13, Mar 31, 2025, 6:50 AM
Reason: formatting

Z K Y

The post below has been deleted. Click to close.

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

816 posts

#17 h Jun 3, 2025, 8:31 PM

Y by

Consider interpolating $q_x$ on $x = 0, \ldots, k$ , where $k$ is the degree of $P(x)$ , to get a polynomial $Q(x)$ with degree at most $k$ . We claim that $q_n = Q(n)$ for all $n$ .

Note that $Q(x) \in \mathbb Q[x]$ , but we can resolve this by simply multiplying by an integer $c$ so that $cQ(x) \in \mathbb Z[x]$ . Next, observe that
$cQ(M) \equiv cQ(n) \equiv cq_n \equiv cq_M \pmod{M-n} \text{ when } n = 0, \ldots, k$ $\implies cQ(M) = cq_M + a \cdot \operatorname{lcm}(M, M-1, \ldots, M-k)$
for some integer $a$ . However, since
$\operatorname{lcm}(M, M-1, \ldots, M-k) = O(n^{d+1}) > O(n^d) \ge Q(m),$
we must have $a=0$ and thus $Q(M) = q_M$ for all sufficiently large $M$ . To finish, if we suppose $N$ is an index which we have not guaranteed $Q(N) = q_N$ , then
$Q(N) \equiv Q(M) = q_M \equiv q_M \implies Q(N) \equiv q_N \pmod{M-N}.$
But since $M-N$ takes infinitely many values, we indeed have $Q(N) = q_N$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

731 posts

#18 h Jul 9, 2025, 9:31 PM

Y by

Let $\deg P = d,$ and determine the rational polynomial satisfying $\deg Q \leq d$ and $Q(k) = d_k$ for $k = 0, 1, \cdots, d.$ This exists by lagrange interpolation.
Suppose $N\cdot Q(k)\in \mathbb Z[x].$ Replace $q_k\to N\cdot q_k.$ All conditions stated within the problem are still satisfied, and if we prove this new sequence doesn’t work, then our original obviously doesn’t work either.
Now, replace $q_k\to q_k - Q(k).$ Thus, $q_k= 0$ for $k = 0, 1, \cdots, d,$ while both conditions must be satisfied as $Q$ is integer polynomial and $m - n \mid Q(m) - Q(n).$
Now, apply $n = 0, 1, \cdots, d$ and we get $\operatorname{lcm}(m, m - 1, \cdots, m - d)|q_m.$ Hence, $|q_m| \geq \operatorname{lcm}(m, \cdots, m - d)$ which grows at $O(n^{d + 1})$ . However, $P$ grows at a speed of $O(n^d),$ so this forces $q$ to be 0 at some sufficiently large value. Take $m$ at this value and we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a