Let $S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$. Prove $|S| < \infty$

Question

Question:

Let $S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$. Prove $|S| < \infty$.

Notice this is not true in $\mathbb R[X]$, as $|x-a|\leq2^x $, $a\in[0,1]$ shows. After experimenting a few rounds on Desmos, I have found no $p(x)\in \mathbb Z[X]$ with degree $\geq3$ satisfy this property. It looks like a piece of cake, but it turns out that the behavior of $|p(x)|$ is quite chaotic (If we drop the absolute value, the problem will become uninteresting). Of course, $2^x$ is going to eventually dominate all polynomials. But how can I prove all but finitely many polynomials dominate $2^x$ at the beginning? I think I've underestimated the difficulty of the problem. Any hint is appreciated.

Follow-up question: Let $S=\{p(x) \in \mathbb Z[X] :|p(x)| \leq 2^x, \forall x\in \mathbb N\}$. Find $|S|$.

Answer 1

Hint: Show that if $f,g\in S$, then the least $n\in\mathbb{N}$ such that $f(n)\neq g(n)$ cannot be too large, by thinking about what you can say about $g(n)-f(n)$.

A full solution is hidden below.

Let $f,g\in S$ be distinct and let $n$ be the least natural number such that $f(n)\neq g(n)$. We can then write $$g(x)=f(x)+x(x-1)(x-2)\dots(x-n+1)h(x)$$ for some polynomial $h$ with integer coefficients such thhat $h(n)\neq 0$. In particular, $|h(n)|\geq1$ so that $$|g(n)-f(n)|\geq n!.$$ But since $f,g\in S$, $|g(n)-f(n)|\leq 2^{n+1}$, and so we must have $2^{n+1}\geq n!$, and so $n\leq 5$.

In other words, any two elements $f,g\in S$ such that $f(x)=g(x)$ for $x=0,1,2\dots,5$ must be equal. Since there are only finitely many possibilities for the values $f(0),f(1),\dots,f(5)$, this shows that $S$ is finite.