Finding a polynomial with $f(i) = a _{i}$ $(i = 1, 2, \dots, n)$ which is monotonic increasing on $[1, n]$

Question

Is there is a positive integer $m$, depending only on $n$, such that for any strictly increasing integer sequence $a _{1}, a _{2}, \dots, a _{n}$, there is some polynomial $f(x)$ of degree at most $m$ with rational coefficients, such that $$f(i) = a_{i} \quad (i = 1, 2, \dots, n)$$ and $f(x)$ is monotonic increasing on $[ 1, n]$?

It feels like using Lagrangian interpolation, $$f(x)=\sum_{i=1}^{n}\left(f(i)\prod_{j\neq i}\dfrac{(x-j)}{(i-j)}\right)=\sum_{i=1}^{n}\left(a_{i}\prod_{j\neq i}\dfrac{(x-j)}{(i-j)}\right)$$ but I find there's no guarantee that this polynomial $f(x)$ will be monotone increasing on $[1,n]$.

Answer 1

No, for $n \geq 3$ there is no such $m$ which applies to all sequences $a_1, \dots, a_n$.

Proposition. If $f$ is a polynomial of degree $d$ with real coefficients, such that $f$ is monotone increasing on $[0, 2]$ with $f(0) = 0$ and $f(1) = 1$, then we must have $f(2) \leq (2d)^{d+1}$.

Proof: Consider the Lagrange interpolation formula for $f(x)$, where we interpolate at the $d+1$ points $0, \frac{1}{d}, \dots, \frac{d-1}{d}, 1$: $$f(x) = \sum_{i=0}^d \left(f(i/d) \prod_{0 \leq j \leq d, j \neq i} \frac{x - j/d}{i/d - j/d}\right)$$

For all $i, j$ we have $0 \leq f(i/d) \leq 1$, $|2 - j/d| \leq 2$, and $|i/d - j/d| \geq 1/d$ (when $i \neq j$), so it follows that $$|f(2)| \leq \sum_{i=0}^d \left(|f(i/d)| \prod_{0 \leq j \leq d, j \neq i} \frac{|2 - j/d|}{|i/d - j/d|}\right) \leq (d+1) \frac{2^d}{(1/d)^d} \leq (2d)^{d+1}$$ as desired.

Then when $n = 3$, for any fixed $m$, using this lemma we see that any polynomial with rational coefficients which satisfies $f(1) = 0$, $f(2) = 1$, and $f(3) = (2m)^{m+1}+1$ and is monotone on $[1, 3]$ must have degree at least $m+1$. This means there is no $m$ for which we can always find a polynomial of degree $\leq m$ to fit any given sequence $a_1, a_2, a_3$.