# Polynomial $P(x)$ such that $P(3k)=2$, $P(3k+1)=1$, $P(3k+2)=0$ for $k=0,1,2,\ldots,n-1$, $P(3n)=2$, and $P(3n+1)=730$

Let $n$ be a positive integer such that there exists a polynomial $P(x)$ over $\mathbb{Q}$ of degree $3n$ satisfying the conditions below: $$P(0) = P(3) = \ldots = P(3n) = 2\,,$$ $$P(1) = P(4) = \ldots= P(3n - 2) = 1\,,$$ $$P(2) = P(5) = \ldots = P(3n - 1) = 0\,,$$ and $$P(3n + 1) = 730\,.$$ Determine the value of $n$.

• Are you familiar with Lagrange interpolation? – Clement C. Feb 8 '14 at 14:38
• No, I'm sure it has a pretty basic solution. Our textbook problems go from easy to difficult, and this is the last one. I was able to solve all the questions, but I'm stumped on this. – Niharika Feb 8 '14 at 14:40
• If you write the Lagrange polynomial interpolating $P$ on the first $3n+1$ points, you get a (unique) polynomial $Q$ of degree $\leq 3n$ satisfying $Q(i)=a_i$ for $i\in\{0,\dots,3n\}$ — so $P=Q$. The extra condition on point $3n+1$ will constrain $n$. – Clement C. Feb 8 '14 at 14:43
• This doesn't seem possible. It looks like $P(k+3) = P(k)$, so $P(3n+1) = P(3n-2) = 1$ which is inconsistent with $P(3n+1) = 730$. – Mitch Feb 8 '14 at 15:14
• The values are congruent modulo 3; besides, the values for 0, 1, 2 are different. That can't be a coincidence... – vonbrand Feb 8 '14 at 15:22

Define the polynomials $$L_i(x) = \underset{j \neq i}{\prod_{0 \le j \le n}} \frac{(x-x_j)}{(x_i - x_j)} = \begin{cases} 1 & \text{ if } x = i \\ 0 & \text{ if } x = j \neq i \end{cases}$$ for each $i \in \{0,1,\cdots,3n\}$. It follows that since the $L_i$'s have degree $3n$, we have (I leave the computations up to you) : $$P(x) = \sum_{i=0}^{3n} P(i) L_i(x) = \sum_{i=0}^n 2 (-1)^{n-i} \binom x{3i} \binom {x-(3i+1)}{3(n-i)} - \sum_{i=0}^{n-1} (-1)^{n-i}\binom x{3i+1}\binom{x-(3i+2)}{3(n-i)-1}.$$ You can evaluate $P(3n+1)$ for a long range using a computer (the notation $\binom xi = x(x-1)\cdots(x-(i-1))/i!$ implies that $\binom xi (n) = \binom ni$ for positive integers). In other words, you are looking for $n$ such that $$730 = P(3n+1) = 2 \sum_{i=0}^n (-1)^{n-i} \binom{3n+1}{3i} - \sum_{i=0}^{n-1} (-1)^{n-i} \binom{3n+1}{3i+1} \\ = \sum_{i=0}^n \left( (-1)^{n-i} \left[ 2\binom{3n+1}{3i} - \binom{3n+1}{3i+1} \right] \right)$$

Hope that helps,

• I believe everything is okay now. I am really troubled though, because the last sum always seems to be of the form $(-1)^{s(n)} 3^{f(n)} + 1$ where $f(n)$ and $s(n)$ are integers. – Patrick Da Silva Feb 8 '14 at 15:46
• Yes, your observation is correct. – Batominovski Jul 23 '18 at 22:30

The OP is equivalent to: given \begin{align} P(x)&=\sum_{i=0}^{3n} a_i x^i \tag{1}\label{1} ,\\ P(3i-2)&=1,\quad i=1,\cdots,n \tag{2}\label{2} ;\\ P(3i-1)&=0,\quad i=1,\cdots,n \tag{3}\label{3} ;\\ P(3i)&=2,\quad i=1,\cdots,n \tag{4}\label{4} ;\\ P(3n+1)&=730 \tag{5}\label{5} ;\\ P(0)&=2 \tag{6}\label{6} , \end{align}

determine $n$.

Conditions \eqref{2}-\eqref{5} define the system of $(3n+1)\times(3n+1)$ linear equations,

\begin{align} Au&=v \tag{7}\label{7} , \end{align}
where $A$ is a special case of the $(3n+1)\times(3n+1)$ Vandermonde matrix

\begin{align} A&=\begin{bmatrix} 1&1&1&\dots &1 \\ 1&2^1&2^2&\dots &2^{3n} \\ 1&3^1&3^2&\dots &3^{3n} \\ \vdots &\vdots &\vdots &\ddots &\vdots \\ 1&(3n+1)^1&(3n+1)^2&\dots &(3n+1)^{3n}\\ \end{bmatrix} ,\\ \text{or }\quad A_{ij}&=(i+1)^{j} ,\quad i,j=0,\cdots,3n . \end{align}

$u$ is the vector of coefficients $a_i$ \begin{align} u&=[a_0,\cdots,a_{3n}]^{\mathsf{T}} , \end{align}

and the right-hand side of \eqref{7} is a vector of the form \begin{align} v&=[\underbrace{1,0,2,1,0,2,\cdots,1,0,2}_{3n},730]^{\mathsf{T}} ,\\ \text{or }\quad v_{3n}&=730 ,\\ v_{i}&= 2-(i+1\mod 3) ,\quad i=0,\cdots,3n-1 . \end{align}

It follows from the condition \eqref{6} that \begin{align} a_0&=2 , \end{align}

For any $n$ all the coefficients $a_i$ of $P(x)$, including $a_0$, can be found as the solution of \eqref{7}.

A quick test reveals that $a_0=2$ for $n=4$.

This is a log of Maxima session for the test:

(%i1) a[i,j]:=(i+1)^j$(%i2) v[i]:=2-mod(i+1,3)$
(%i3) n:4$(%i4) A:apply('matrix,makelist(makelist(a[i,j],j,0,3*n),i,0,3*n))$
(%i5) V:makelist(v[i],i,0,3*n)$(%i6) V[3*n+1]:730$
(%i7) V;
(%o7)              [1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 730]
(%i8) a0=invert(A)[1] . V;
(%o8)                               a0 = 2


Let $\omega:=\exp\left(\frac{2\pi\text{i}}{3}\right)=\frac{-1+\sqrt{-3}}{2}$. Define $$\tau(z):=\left(\frac{1-\omega^2}{3}\right)z^2+\left(\frac{1-\omega}{3}\right)z+1\text{ for all }z\in\mathbb{C}\,.$$ Note that, for each $k\in\mathbb{Z}$, we have $$\tau(\omega^k)=\left\{ \begin{array}{ll} 2&\text{if }k\equiv0\pmod{3}\,,\\ 1&\text{if }k\equiv1\pmod{3}\,,\\ 0&\text{if }k\equiv2\pmod{3}\,. \end{array} \right.$$

It is well known (see also here) that, if $f(x)\in \mathbb{K}[x]$ is a polynomial over a field $\mathbb{K}$ of degree $d$, then $$\sum_{r=0}^{d+1}\,(-1)^r\,\binom{d+1}{r}\,f(x+r)\equiv 0\,.$$ From the result above, we have that $$\sum_{r=0}^{3n+1}\,(-1)^r\,\binom{3n+1}{r}\,P(r)=0\,.$$ Recall that $P(r)=\tau(\omega^r)$ for $r=0,1,2,\ldots,3n$, and $P(3n+1)=3^6+1=3^6+\tau(\omega^{3n+1})$. That is, $$\sum_{r=0}^{3n+1}\,(-1)^r\,\binom{3n+1}{r}\,\tau(\omega^r)=(-1)^{3n}\,3^6\,.$$ Ergo, $$\left(\frac{1-\omega^2}{3}\right)\left(1-\omega^2\right)^{3n+1}+\left(\frac{1-\omega}{3}\right)\left(1-\omega\right)^{3n+1}+1(1-1)^{3n+1}=(-1)^{3n}3^6\,.$$ Thus, $$2\,\text{Re}\left((1-\omega)^{3n+2}\right)=\left(1-\omega^2\right)^{3n+2}+\left(1-\omega\right)^{3n+2}=(-1)^{3n}3^7\,.$$ Since $1-\omega=\sqrt{-3}\,\omega^2$, we see that $$(1-\omega)^{3n+2}=\sqrt{-3}^{3n+2}\omega^{6n+4}=\sqrt{-3}^{3n+2}\omega\,.$$ Therefore, $$3^{\frac{3n+2}{2}}\,\text{Re}\left(\sqrt{-1}^{3n+2}\omega\right)=\text{Re}\left(\sqrt{-3}^{3n+2}\omega\right)=(-1)^{3n}\frac{3^7}{2}\,.$$ Since $\frac{1}{2}\leq \Big|\text{Re}\left(\sqrt{-1}^{3n+2}\omega\right)\Big|\leq\frac{\sqrt{3}}{2}$, we have that $$\frac{3^{\frac{3n+2}{2}}}{2}\leq \frac{3^7}{2} \leq \frac{3^{\frac{3n+3}{2}}}{2}\,.$$ Consequently, $$3n+2\leq 14\leq 3n+3\,.$$ This proves that $n=4$ is the only possibility. It is not difficult to see that $n=4$ indeed works.

• hi there, forgive my ignorance but the identity directly following bit "It is well known that...", I've never seen before. Is this considered an elementary result? would you be able to link me to somewhere I can read about it? – Merk Zockerborg Jul 24 '18 at 5:56
• I have seen questions about this identity a few times on this site, but I can't find them. People who have done numerical methods are probably familiar with the identity. However, I can explain it to you. Basically, you start with the forward differencing operator $\Delta$ defined by $$\Delta f(x):=f(x+1)-f(x)\,.$$ This operator reduces the degree of a polynomial by $1$. Hence, if your polynomial $f(x)$ is of degree $d$, then $\Delta^{d+1}f(x)$ must be identically zero. You also have $$\Delta^df(x)=d!\,F\,,$$ where $F$ is the leading coefficient of $f$. – Batominovski Jul 24 '18 at 8:13
• Actually, I don't know field K. It's not learned in high school. – Takahiro Waki Jul 29 '18 at 9:41
• This is an elementary method. You only need to know a few things about complex numbers and polynomials, as well as the Binomial Theorem. Just because it is a complicated solution, it doesn't mean the solution isn't elementary. There are much more complicated problems for high schoolers than this. – Batominovski Jul 29 '18 at 9:42
• @TakahiroWaki The Nørlund–Rice Identity does not require any knowledge about fields. I only stated it so people know that it works over an arbitrary field. For whatever it's worth, just take $\mathbb{R}$ for $\mathbb{K}$ in this problem. Also, if you are a high school student who wants to learn advanced mathematics, it's your loss if you don't try to get yourself accustomed to notions like fields. Ignorance is not an excuse not to learn. – Batominovski Jul 29 '18 at 9:47