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$

Question

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$.

Answer 1

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,