Proof of Growth Bound for a Polynomial Function on the Real Line

Throughout, $S$ is the successor map of Natural Numbers and $[N]$ is the initial segment determined by $N$.

Step 0 (adding a fixed element to an inequality). If $a,b,e\in\mathbb{R}$ and $a\le b$, then $a+e\le b+e$. Indeed, either $a=b$, and then $a+e=b+e$, or $a<b$, and then $a+e<b+e$ by claim 1 of Elementary Order Arithmetic in an Ordered Field.

Step 1 (claim 1). Fix $t\in\mathbb{R}$ with $1\le t$. By claim 6 of Elementary Order Arithmetic in an Ordered Field we have $0<1$, hence $0<t$ by claim 2 of that lemma, and therefore $0\le t^{n}$ for every $n\in\mathbb{N}$ by claim 5 of Properties of Natural Number Powers in a Field.

First, $t^{n}\le t^{S(n)}$ for every $n\in\mathbb{N}$: by claim 1 of Properties of Natural Number Powers in a Field, $t^{S(n)}=t^{n}t$, while multiplying the inequality $1\le t$ by the nonnegative element $t^{n}$ gives $t^{n}\cdot 1\le t^{n}t$ by claim 5 of Elementary Arithmetic in an Ordered Field.

Now let $E$ be the set of those $n\in\mathbb{N}$ such that $t^{m}\le t^{n}$ for every $m\in\mathbb{N}$ with $m\le n$. If $m\le 1$ then $1\le m$ by claim 4 of Properties of the Order on the Natural Numbers, hence $m=1$ by claim 2 of that lemma, and $t^{m}=t^{1}$; so $1\in E$. Let $n\in E$ and let $m\le S(n)$. If $m=S(n)$ there is nothing to prove; otherwise $m\le n$ by claim 5 of Properties of the Order on the Natural Numbers, so $t^{m}\le t^{n}\le t^{S(n)}$ by $n\in E$ and the previous paragraph, together with transitivity of the order of $\mathbb{R}$, which is a total order by the definition of an ordered field. Hence $S(n)\in E$, and $E=\mathbb{N}$ by Principle of Induction for the Natural Numbers.

Step 2 (claim 2). By Polynomial Function on a Field fix $N\in\mathbb{N}$, $c_{0}\in\mathbb{R}$ and $c:[N]\to\mathbb{R}$ with $p(x)=c_{0}+\sum_{k=1}^{N}c_{k}x^{k}$ for every $x\in\mathbb{R}$, the sum being the finite sum of $\mathbb{R}$. Put

$$C=|c_{0}|+\sum_{k=1}^{N}|c_{k}| .$$

By claim 1 of Properties of the Absolute Value in an Ordered Field each $|c_{k}|$ and $|c_{0}|$ is nonnegative, so $0\le C$ by claim 5 of Properties of Finite Sums and claim 2 of Elementary Arithmetic in an Ordered Field.

Let $t\in\mathbb{R}$ with $1\le t$; as in Step 1, $0<t$ and $0\le t^{k}$ for every $k\in\mathbb{N}$. By claim 1 of Properties of the Absolute Value in an Ordered Field we then have $|t^{k}|=t^{k}$, and by claim 4 of that lemma $|c_{k}t^{k}|=|c_{k}|\,t^{k}$.

For $k\in[N]$ we have $k\le N$, so $t^{k}\le t^{N}$ by claim 1, and multiplying by the nonnegative element $|c_{k}|$ gives $|c_{k}|t^{k}\le|c_{k}|t^{N}$ by claim 5 of Elementary Arithmetic in an Ordered Field. Hence, by claim 1 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers and claim 3 of Properties of Finite Sums,

$$\sum_{k=1}^{N}|c_{k}|\,t^{k}\le\sum_{k=1}^{N}|c_{k}|\,t^{N}=\Bigl(\sum_{k=1}^{N}|c_{k}|\Bigr)t^{N}.$$

Also $1\le N$ by claim 4 of Properties of the Order on the Natural Numbers, so $t=t^{1}\le t^{N}$ by claim 1 and claim 1 of Properties of Natural Number Powers in a Field; since $1\le t$, transitivity gives $1\le t^{N}$, and multiplying by the nonnegative element $|c_{0}|$ gives $|c_{0}|\le|c_{0}|t^{N}$ by claim 5 of Elementary Arithmetic in an Ordered Field.

Finally, by claim 5 of Properties of the Absolute Value in an Ordered Field and claim 2 of Comparison and Absolute Value Bounds for Finite Sums of Real Numbers,

$$|p(t)|\le|c_{0}|+\Bigl|\sum_{k=1}^{N}c_{k}t^{k}\Bigr|\le|c_{0}|+\sum_{k=1}^{N}|c_{k}|\,t^{k}.$$

By Step 0, adding $\sum_{k=1}^{N}|c_{k}|t^{k}$ to the inequality $|c_{0}|\le|c_{0}|t^{N}$ gives $|c_{0}|+\sum_{k=1}^{N}|c_{k}|t^{k}\le|c_{0}|t^{N}+\sum_{k=1}^{N}|c_{k}|t^{k}$, and adding $|c_{0}|t^{N}$ to the inequality $\sum_{k=1}^{N}|c_{k}|t^{k}\le\bigl(\sum_{k=1}^{N}|c_{k}|\bigr)t^{N}$ established above gives $|c_{0}|t^{N}+\sum_{k=1}^{N}|c_{k}|t^{k}\le|c_{0}|t^{N}+\bigl(\sum_{k=1}^{N}|c_{k}|\bigr)t^{N}$. Chaining these with the previous display, using transitivity and distributivity, we obtain

$$|p(t)|\le|c_{0}|t^{N}+\Bigl(\sum_{k=1}^{N}|c_{k}|\Bigr)t^{N}=C\,t^{N},$$

as required.