A good problem .It can be prove by Lagrange with n nut $ 1,2,...,n$ if deg P<n.

TTsphn wrote: A good problem .It can be prove by Lagrange with n nut $ 1,2,...,n$ if deg P<n. Please explain more. Or provide a more elementary solution.

Suppose $ f$ is a polynomial of degree less than $ n$. The polynomial \[ \sum_{k=0}^n f(k)\prod_{j\neq k} \frac{x-j}{k-j}\] is the unique polynomial of degree less than or equal to $ n$ given the values of $ f(k)$ for $ k=0,1,\cdots, n$. So that polynomial must be $ f$ and the $ x^n$ term must be 0. Therefore, \[ 0=\sum_{k=0}^n \frac{f(k)}{\prod_{j\neq k} (k-j)}=\sum_{k=0}^n \frac{(-1)^{n-k}}{k!(n-k)!}f(k)=\frac{1}{n!}\sum_{k=0}^n (-1)^{n-k}\binom{n}{k}f(k)\] But we have $ t^k-1<f(k)<t^k+1$ for all $ k$, so that \[ 0>(t^n-1)\binom{n}{n}+(t^{n-2}-1)\binom{n}{n-2}+\cdots\] \[ -(t^{n-1}+1)\binom{n}{n-1}-(t^{n-3}+1)\binom{n}{n-3}-\cdots\] \[ =(t-1)^n-2^n\geq 0\] a contradiction. So $ f$ must have degree at least $ n$.

scorpius119 wrote: The polynomial \[ \sum_{k = 0}^n f(k)\prod_{j\neq k} \frac {x - j}{k - j} \] is the unique polynomial of degree less than or equal to $ n$ given the values of $ f(k)$ for $ k = 0,1,\cdots, n$. What do you mean here?

Suppose $ P(x)=\sum_{k=0}^n f(k)\prod_{j\neq k} \frac{x-j}{k-j}$. Observe that each of the products $ \prod_{j\neq k} \frac{x-j}{k-j}$ have degree $ n$, so $ P$ has degree at most $ n$. Also, $ P(0)=f(0)$ because the product in the 0th term in the sum is $ \frac{-1}{-1}\cdot \frac{-2}{-2}\cdot \cdots \frac{-n}{-n}=1$ and the product in the $ k$th term for $ k\neq 0$ is $ \frac{0}{-k}\cdot \text{whatever}=0$. In a similar way, $ P(1)=f(1),P(2)=f(2),\cdots P(n)=f(n)$. If $ z(x)=P(x)-f(x)$, then $ z$ has degree at most $ n$ but $ n+1$ roots, so must be the zero polynomial, giving $ f(x)=P(x)$. Of course, $ P$ usually will have degree $ n$, so the condition that $ f$ has degree strictly less than $ n$ requires the $ x^n$ coefficient of $ f$ to be 0.

Define the polynomial $ \binom{x}{n}: ={x(x-1)\cdots(x-n+1)\over n!}$ for $ n\in\mathbb{N}$ and $ \binom{x}{0}\equiv 1$. Then $ f_n(x)=2^n\binom{x}{n-1}+2^{n-2}\binom{x}{n-3}+\cdots=\sum_{i=0}^n (1-(-1)^{n-i})2^i\binom{x}{i}$ has degree $ n-1$ and leading coefficient $ {2^n\over (n-1)!}$ for all $ n\in\mathbb{N}$, and for all $ k=0,1,\ldots,n$ we have $ f_n(k)=\sum_{i=0}^k (1-(-1)^{n-i})2^i\binom{k}{i}=(2+1)^k-(2-1)^k$. So $ f_n(k)-3^k=(-1)^{k+1}$ and $ |f_n(k)-3^k|=1$ for all $ k=0,1,\ldots ,n$. scorpius119's argument shows, that this is in fact the only polynomial $ f$ of degree $ <n$ with $ |f(k)-t^k|\le 1$ for all $ k=0,1,\ldots,n$ and some $ t\ge 3$. Nice!

You are really intelligent Scorpius119 So wonderful Nice and short solution