finite polynomials satisfy $|f(x)|\le 2^x$

Question

This is a problem from TsingHua University math competition for high school students.

Prove there exists only finite number of polynomials $f\in \mathbb{Z}[x]$ such that for any $x\in \mathbb{N}$ , $|f(x)|\le 2^x$.

My attempts: since $f(x)=o(2^x)$, $f$ can only be bounded when $x$ is small, for example $f(0)=0,1, \ \ f(1)=0,1,2, \cdot \cdot \cdot$. Thus using Lagrange interpolation it concludes that for any given $n\in \mathbb{N}$ the number for such polynomial is finite. But I don't know how to proceed from here.

Is my methods wrong or there's a better way? Also, I'd like to know something about the background of this problem. Thanks in advance.

Answer 1

Solution credits to Rui Yao:

According to a property of finite differences, if we set $c_n\in \mathbb{Z}$ to be the highest coefficient of $f(x)$, which has degree $n$, then $$n!c_n=\Delta ^n [f](x)=\sum_{i=0}^{n}\binom{n}{i} f(i)(-1)^{n-i}$$ Thus $$|n!c_n|=|\sum_{i=0}^{n}\binom{n}{i} f(i)(-1)^{n-i}|\le \sum_{i=0}^{n}|\binom{n}{i} f(i)(-1)^{n-i}|\le \sum_{i=0}^{n}2^i\binom{n}{i}=3^n$$ Combined with $c_n\in \mathbb{Z}/{0}$ this leads to $n\le 6$.

Since we've proved that for any given degree $n$ there's only finite number of polynomials satisfy the condition, we can conclude that the polynomial satisfy the condition is finite.