Problem of the Month
Solution to Problem 4: A Polynomial Sandwich

1. We present two solutions to Problem 1. In both solutions, we will use the so called triangle inequality. This frequently useful fact says that if $u$ and $v$ are real numbers, then $$|u+v|\le |u|+|v|$$ where $|x|$ represents the absolute value of the real number $x$. The triangle inequality can be applied twice to get that $|u+v+w|\le |u|+|v|+|w|$ for any real numbers $u,v,$ and $w$. If you are unfamiliar with the triangle inequality or even with absolute values, this might be a good time for an internet search!

   Solution 1:

   We will prove the following fact: If $p(x)=A{x}^3+B{x}^2+Cx+D$ with real numbers $A,B,C,$ and $D$ and $A\ne 0$, then there are infinitely many integers $n$ such that $p(n)>0$ and infinitely many integers $m$ such that $p(m)<0$.

   Then $a={\displaystyle \frac{1}{3}}$ can be deduced from this fact. To see this, consider the polynomial $$\begin{array}{rl}q(x)& =f(x)-({\displaystyle \frac{1}{3}}{x}^3+x^2+2x+{\displaystyle \frac{4}{3}})\\ & =(a-{\displaystyle \frac{1}{3}})x^3+(b-1)x^2+(c-2)x+(d-{\displaystyle \frac{4}{3}}).\end{array}$$ Using the given information, $q(n)\le 0$ for every integer $n$ with the possible exception of $n=-2$. This means $q(n)>0$ for at most one integer. By the fact above, if $a-{\displaystyle \frac{1}{3}}$ were different from $0$, then there would be infinitely many integers $n$ with $q(n)>0$. This means we must have $a-{\displaystyle \frac{1}{3}}=0$.

   Interestingly, we have only used one of the two inequalities given in the problem. To understand why we can only use one of the inequalities, you may want to reread the hint for this problem and think about what the inequalities say when $n$ is negative versus when $n$ is positive.

   To prove the fact above, set $M=max\{|B|,|C|,|D|\}$. In particular, this means $M$ is at least as large as each of $|B|,|C|,$ and $|D|$.

   If $B=C=D=0$, then $p(n)>0$ when $n>0$ and $p(m)<0$ when $m<0$ or vice versa, depending on the sign of $A$. For the rest of the proof, we assume not all of $B,C,$ and $D$ are zero, which means $M>0$.

   For any nonzero integer $n$, using the triangle inequality and the fact that $1\le |n|\le |n{|}^2\le |n{|}^3$ we get that $$\begin{array}{rl}|B{n}^2+Cn+D|& \le |B{n}^2|+|Cn|+|D|\\ & =|B||n{|}^2+|C||n|+|D|\\ & \le |B||n{|}^2+|C||n{|}^2+|D||n{|}^2\\ & \le M|n{|}^2+M|n{|}^2+M|n{|}^2\\ & =3M|n{|}^2.\end{array}$$ If $u$ and $v$ are real numbers with $v$ positive, the inequality $|u|\le v$ is really saying that $-v\le u\le v$. Since $3M|n{|}^2$ is positive, the chain of inequalities above implies that $$-3M|n{|}^2\le B{n}^2+Cn+D\le 3M|n{|}^2.$$ Adding $A{n}^3$ to this chain of inequalities gives $$\begin{array}{}\text{(}\ast \text{)}& A{n}^3-3M|n{|}^2& \le p(n)\le A{n}^3+3M|n{|}^2\end{array}$$ for all nonzero integers $n$.

   We will use these inequalities to show that as long as $A\ne 0$, there are infinitely many integers $n$ with $p(n)>0$ and infinitely many integers $m$ with $p(m)<0$.

   First, suppose $A>0$. In this case, choose any positive integer $n>{\displaystyle \frac{3M}{A}}$. There are infinitely many such $n$ since $M$ and $A$ are constants. Noting that $0<n^2=|n{|}^2$, this implies $n^3>{\displaystyle \frac{3M}{A}}|n{|}^2$. Since $A>0$, we can multiply both sides by $A$ and rearrange to get $0<A{n}^3-3M|n{|}^2$. Combining with $(\ast )$, this implies $p(n)>0$ for any positive integer $n>{\displaystyle \frac{3M}{A}}$.

   Now choose any negative integer $m<{\displaystyle \frac{-3M}{A}}$. As in the previous paragraph, $0<m^2=|m{|}^2$, which implies $m^3<-{\displaystyle \frac{3M}{A}}|m{|}^2$, which can be rearranged to $A{m}^3+3M|m{|}^2<0$. Combining with $(\ast )$, gives $p(m)<0$ for any negative integer $m<{\displaystyle \frac{-3M}{A}}$, and there are infinitely many such $m$.

   In a similar manner we can deal with the case of $A<0$, proving the fact is true for all $A\ne 0$.

   Solution 2:

   We will assume that $a\ne {\displaystyle \frac{1}{3}}$ and deduce a contradiction. First, assume $a>{\displaystyle \frac{1}{3}}$. By rearranging the inequality $$a{n}^3+b{n}^2+cn+d\le {\displaystyle \frac{1}{3}}{n}^3+n^2+2n+{\displaystyle \frac{4}{3}},$$ which holds for all integers except possibly $n=-2$, we get $$(a-{\displaystyle \frac{1}{3}})n^3\le (1-b)n^2+(2-c)n+{\displaystyle \frac{4}{3}}-d.$$ Multiplying through by $3$ gives $$(3a-1)n^3\le 3(1-b)n^2+3(2-c)n+4-3d.$$ Dividing through by $n^3$ gives $$3a-1\le {\displaystyle \frac{3(1-b)}{n}}+{\displaystyle \frac{3(2-c)}{n^2}}+{\displaystyle \frac{(4-3d)}{n^3}},$$ but we are only guaranteed that this inequality holds for positive integers $n$ since the original inequality may fail at $n=-2$, and dividing by a negative integer $n$ would have reversed the inequality.

   For any real number $u$, we have $u\le |u|$, which means $$3a-1\le \left|{\displaystyle \frac{3(1-b)}{n}}\right|+\left|{\displaystyle \frac{3(2-c)}{n^2}}\right|+\left|{\displaystyle \frac{(4-3d)}{n^3}}\right|.$$ Noting that ${\displaystyle \frac{1}{n^2}}<{\displaystyle \frac{1}{n}}$ and ${\displaystyle \frac{1}{n^3}}<{\displaystyle \frac{1}{n}}$ for all integers $n>1$, we get $$\begin{array}{rl}3a-1& \le \left|{\displaystyle \frac{3(1-b)}{n}}\right|+\left|{\displaystyle \frac{3(2-c)}{n^2}}\right|+\left|{\displaystyle \frac{(4-3d)}{n^3}}\right|\\ & =|3(1-b)|{\displaystyle \frac{1}{n}}+|3(2-c)|{\displaystyle \frac{1}{n^2}}+|(4-3d)|{\displaystyle \frac{1}{n^3}}\\ & <|3(1-b)|{\displaystyle \frac{1}{n}}+|3(2-c)|{\displaystyle \frac{1}{n}}+|(4-3d)|{\displaystyle \frac{1}{n}}\\ & ={\displaystyle \frac{1}{n}}(|3(1-b)|+|3(2-c)|+|(4-3d)|)\end{array}$$ and so $$\begin{array}{}\text{(}\ast \ast \text{)}& 3a-1& <{\displaystyle \frac{1}{n}}(|3(1-b)|+|3(2-c)|+|(4-3d)|)\end{array}$$ for every integer $n>1$. Recall that $a>{\displaystyle \frac{1}{3}}$ which implies $3a-1>0$. If $|3(1-b)|+|3(2-c)|+|(4-3d)|$ is equal to 0, then $(\ast \ast )$ says that something positive is less than 0, which can never happen. Otherwise, the quantity $|3(1-b)|+|3(2-c)|+|(4-3d)|$ is some positive number, which means that by taking $n$ large enough, we can force $${\displaystyle \frac{1}{n}}(|3(1-b)|+|3(2-c)|+|(4-3d)|)<3a-1$$ which violates $(\ast \ast )$ as well. In other words, $(\ast \ast )$ can only hold for finitely many positive integers $n$. However, the assumption $a>{\displaystyle \frac{1}{3}}$ implies that $(\ast \ast )$ holds for all positive integers. This means it must not be the case that $a>{\displaystyle \frac{1}{3}}$ so we conclude that $a\le {\displaystyle \frac{1}{3}}$.

   Similarly, if we assume $a<{\displaystyle \frac{1}{3}}$, we can use the other inequality to derive a contradiction. When doing this, one would need to be careful to take $n<-2$ since the assumed inequality is not guaranteed to hold for $n=-2$.

   If you have learned a bit about limits in a calculus course, you might want to think about how this relates to the Squeeze Theorem. In fact, the Squeeze Theorem can be used to give a very short proof that $a={\displaystyle \frac{1}{3}}$.

2. Since $${\displaystyle \frac{1}{3}}{n}^3-n-{\displaystyle \frac{2}{3}}\le f(n)\le {\displaystyle \frac{1}{3}}{n}^3+n^2+2n+{\displaystyle \frac{4}{3}},$$ for all integers (except possibly $n=-2$), this chain of inequalities provides an interval in which $f(n)$ lies for each integer $n\ne -2$. Since $f(n)$ is an integer, this will give a finite number of possible values of $f(n)$. By finding integers $n$ for which there are a small number of possibilities for $f(n)$, we will be able to find a finite list of possibilities for $f(x)$. To help with this, consider the polynomial $$h(x)=({\displaystyle \frac{1}{3}}{x}^3+x^2+2x+{\displaystyle \frac{4}{3}})-({\displaystyle \frac{1}{3}}{x}^3-x-{\displaystyle \frac{2}{3}})=x^2+3x+2.$$ For an integer $n$, $h(n)$ is the length of the interval containing $f(n)$. Integers $n$ where $h(n)$ is small will have a small number of possibilities for the value of $f(n)$.

   Notice that $h(x)=(x+1)(x+2)$, so we expect $h(n)$ to be smallest when $n$ is either equal to or near $-1$ and $-2$. We are not guaranteed that the inequalities hold for $n=-2$. Therefore, we will substitute $n=-1$, $n=0$, and $n=-3$.

   When $n=-1$, $$\begin{array}{rl}{\displaystyle \frac{1}{3}}(-1{)}^3-(-1)-{\displaystyle \frac{2}{3}}& \le f(-1)\le {\displaystyle \frac{1}{3}}(-1{)}^3+(-1{)}^2+2(-1)+{\displaystyle \frac{4}{3}}\\ \\ 0& \le f(-1)\le 0\end{array}$$ which means $f(-1)=0$.

   When $n=0$, we have $$\begin{array}{rl}{\displaystyle \frac{1}{3}}(0{)}^3-(0)-{\displaystyle \frac{2}{3}}& \le f(0)\le {\displaystyle \frac{1}{3}}(0{)}^3+(0{)}^2+2(0)+{\displaystyle \frac{4}{3}}\\ \\ -{\displaystyle \frac{2}{3}}& \le f(0)\le {\displaystyle \frac{4}{3}}\end{array}$$ and since $f(0)$ is an integer, this means $f(0)=0$ or $f(0)=1$.

   Finally, with $n=-3$, we get $$\begin{array}{rl}{\displaystyle \frac{1}{3}}(-3{)}^3-(-3)-{\displaystyle \frac{2}{3}}& \le f(-3)\le {\displaystyle \frac{1}{3}}(-3{)}^3+(-3{)}^2+2(-3)+{\displaystyle \frac{4}{3}}\\ \\ -{\displaystyle \frac{20}{3}}& \le f(-3)\le -{\displaystyle \frac{14}{3}}\end{array}$$ and since $f(-3)$ must be an integer, we get that $f(-3)$ is either $-6$ or $-5$.

   We can translate this into information about the unknown coefficients, $b$, $c$, and $d$ of $f(n)$. From $f(-1)=0$, we get $$0={\displaystyle \frac{1}{3}}(-1{)}^3+b(-1{)}^2+c(-1)+d=-{\displaystyle \frac{1}{3}}+b-c+d$$ or $b-c+d={\displaystyle \frac{1}{3}}$.

   Substituting $n=0$, we have that $f(0)=d$, which implies $d=0$ or $d=1$.

   Since $f(-3)=-5$ or $f(-3)=-6$ and $$f(-3)={\displaystyle \frac{1}{3}}(-3{)}^3+b(-3{)}^2+c(-3)+d=-9+9b-3c+d.$$ it must be that $9b-3c+d=4$ or $9b-3c+d=3$. This means $b$, $c$, and $d$ satisfy one of the following four systems of equations:

   $$\begin{array}{rl}b-c+d& ={\displaystyle \frac{1}{3}}\\ 9b-3c+d& =3\\ d& =0\end{array}$$

   $$\begin{array}{rl}b-c+d& ={\displaystyle \frac{1}{3}}\\ 9b-3c+d& =3\\ d& =1\end{array}$$

   $$\begin{array}{rl}b-c+d& ={\displaystyle \frac{1}{3}}\\ 9b-3c+d& =4\\ d& =0\end{array}$$

   $$\begin{array}{rl}b-c+d& ={\displaystyle \frac{1}{3}}\\ 9b-3c+d& =4\\ d& =1\end{array}$$

   Consider the first system. If $d=0$ is substituted into the first two equations, they simplify to $b-c={\displaystyle \frac{1}{3}}$ and $9b-3c=3$. Multiplying the first of these resulting equations by $3$ gives $3b-3c=1$, which can be subtracted from $9b-3c=3$ to get $6b=2$ or $b={\displaystyle \frac{1}{3}}$. Since $b-c={\displaystyle \frac{1}{3}}$, this means $c=0$. Therefore, one possibility for the polynomial $f(x)$ is $f(x)={\displaystyle \frac{1}{3}}{x}^3+{\displaystyle \frac{1}{3}}{x}^2$.

   The other three systems can be solved in a similar way. This gives a total of four possibilities for $f(x)$ which are listed below in factored form: $$\begin{array}{rl}{\displaystyle \frac{1}{3}}{x}^3+{\displaystyle \frac{1}{3}}{x}^2& ={\displaystyle \frac{1}{3}}{x}^2(x+1)\\ \\ {\displaystyle \frac{1}{3}}{x}^3+{\displaystyle \frac{2}{3}}{x}^2+{\displaystyle \frac{4}{3}}x+1& ={\displaystyle \frac{1}{3}}(x+1)(x^2+x+3)\\ \\ {\displaystyle \frac{1}{3}}{x}^3+{\displaystyle \frac{1}{2}}{x}^2+{\displaystyle \frac{1}{6}}x& ={\displaystyle \frac{1}{6}}x(x+1)(2x+1)\\ \\ {\displaystyle \frac{1}{3}}{x}^3+{\displaystyle \frac{5}{6}}{x}^2+{\displaystyle \frac{3}{2}}x+1& ={\displaystyle \frac{1}{6}}(x+1)(2x^2+3x+6)\end{array}$$

   When $n=1$ is substituted into the first, second, and fourth polynomials, the outputs are ${\displaystyle \frac{2}{3}}$, ${\displaystyle \frac{10}{3}}$, and ${\displaystyle \frac{11}{3}}$, respectively. None of these are integers, which means $f(x)$ cannot be any of these three polynomials since $f(n)$ must be an integer when $n$ is an integer. Therefore, the only possibility is that $$f(x)={\displaystyle \frac{1}{3}}{x}^3+{\displaystyle \frac{1}{2}}{x}^2+{\displaystyle \frac{1}{6}}x={\displaystyle \frac{x(x+1)(2x+1)}{6}}.$$

   We now verify that $f(x)$ has the properties claimed in the question.

   To see that $f(n)$ is an integer for every integer $n$, we will show that $n(n+1)(2n+1)$, the numerator of $f(n)$, must be a multiple of $6$. Since $n$ and $n+1$ are consecutive integers, one of them must be even. This means $n(n+1)(2n+1)$ is even. If either $n$ or $n+1$ is a multiple of $3$, then $n(n+1)(2n+1)$ is a multiple of $3$. If neither $n$ nor $n+1$ is a multiple of $3$, then $n$ must be 1 more than a multiple of $3$. That is, there is some integer $k$ so that $n=3k+1$. Then $2n+1=2(3k+1)+1=6k+3=3(2k+1)$, so $2n+1$ is a multiple of $3$. This shows that $n(n+1)(2n+1)$ must be a multiple of $3$. Therefore, $$f(n)={\displaystyle \frac{n(n+1)(2n+1)}{6}}$$ is an integer for every integer $n$. You may recognize that $f(n)=1^2+2^2+3^2+\cdots +n^2$, which immediately implies $f(n)$ is an integer.

   Next, we will show that ${\displaystyle \frac{1}{3}}{n}^3-n-{\displaystyle \frac{2}{3}}\le f(n)$ or $${\displaystyle \frac{1}{3}}{n}^3-n-{\displaystyle \frac{2}{3}}\le {\displaystyle \frac{1}{3}}{n}^3+{\displaystyle \frac{1}{2}}{n}^2+{\displaystyle \frac{1}{6}}n$$ for all integers $n$ with the possible exception of $n=-2$. After rearranging, this inequality is equivalent to $$0\le {\displaystyle \frac{1}{2}}{n}^2+{\displaystyle \frac{7}{6}}n+{\displaystyle \frac{2}{3}}.$$ Since $6$ is positive, the inequality is also equivalent to $$0\le 6({\displaystyle \frac{1}{2}}{n}^2+{\displaystyle \frac{7}{6}}n+{\displaystyle \frac{2}{3}})=3n^2+7n+4=(3n+4)(n+1).$$ The polynomial $(3x+4)(x+1)$ is quadratic and has roots $x=-1$ and $x=-{\displaystyle \frac{4}{3}}$. The leading coefficient is positive, which means it can only take negative values strictly between $-{\displaystyle \frac{4}{3}}$ and $-1$. There are no integers in this range, which means $(3n+4)(n+1)\ge 0$ for all integers $n$. Thus, the original inequality also holds for all integers $n$ including $n=-2$.

   Now consider the polynomial $(x+1)(3x+8)$ which has roots $x=-{\displaystyle \frac{8}{3}}$ and $x=-1$. The only integer $n$ for which $(n+1)(3n+8)$ is negative is $n=-2$ since $-2$ is the only integer between $-{\displaystyle \frac{8}{3}}$ and $-1$. Therefore, for all integers $n\ne -2$, we have $$0\le (n+1)(3n+8)$$ which we expand and divide by $6$ to get $$0\le {\displaystyle \frac{1}{2}}{n}^2+{\displaystyle \frac{11}{6}}n+{\displaystyle \frac{4}{3}}.$$ After rearranging and adding ${\displaystyle \frac{1}{3}}{n}^3$ to both sides, we have that $$f(n)={\displaystyle \frac{1}{3}}{n}^3+{\displaystyle \frac{1}{2}}{n}^2+{\displaystyle \frac{1}{6}}n\le {\displaystyle \frac{1}{3}}{n}^3+n^2+2n+{\displaystyle \frac{4}{3}}$$ for all integers $n\ne -2$. Combining this with the other inequality, we have now shown that $${\displaystyle \frac{1}{3}}{n}^3-n-{\displaystyle \frac{2}{3}}\le f(n)\le {\displaystyle \frac{1}{3}}{n}^3+n^2+2n+{\displaystyle \frac{4}{3}}$$ for all integers $n\ne -2$.

   Finally, let’s compute $f({10}^{2025})-f({10}^{2025}-1)$. To do this, we will work out $f(n)-f(n-1)$ for general $n$ and substitute $n={10}^{2025}$ into the resulting expression. $$\begin{array}{rl}f(n)-f(n-1)& ={\displaystyle \frac{n(n+1)(2n+1)}{6}}-{\displaystyle \frac{(n-1)[(n-1)+1][2(n-1)+1]}{6}}\\ & ={\displaystyle \frac{n[(n+1)(2n+1)-(n-1)(2n-1)]}{6}}\\ & ={\displaystyle \frac{n(2n^2+n+2n+1-2n^2+n+2n-1)}{6}}\\ & ={\displaystyle \frac{n(6n)}{6}}\\ & =n^2\end{array}$$ Therefore, $f({10}^{2025})-f({10}^{2025}-1)=({10}^{2025}{)}^2={10}^{4050}$. As mentioned earlier, the polynomial $f(x)$ has the special property that $f(n)=1^2+2^2+3^2+\cdots +n^2$ for every $n\ge 1$. It follows from this property that $f(n)-f(n-1)=n^2$.

Notice that we used the fact that $n\ne -2$ to prove the inequality $f(n)\le \frac{1}{3}{n}^3+n^2+2n+\frac{4}{3}$. It is worth thinking about what happens at $n=-2$, and seeing if you can figure out why we had to exclude $n=-2$.