MIT PRIMES Question, polynomial satisfying conditions

There was an MIT PRIMES application problem that goes like this: (don't worry, the admission ended on Dec 1, so I'm not cheating or anything)

For all $d\geq 0$, determine if there is a polynomial $p(x)$ with degree $d$ such that for all $n$ in $1\ldots 99$ inclusive satisfies $$p(n)=n+\frac1n$$ and if so, what is $p(x)$ and find the value of $p(100)$.

In English terms: find a polynomial with degree $d$ such that $$p(1)=1+\frac11=2$$ $$p(2)=2+\frac12=2.5$$ and so on. What values of $d$ work? What are the polynomials for each of those $d$? What is $p(100)$ for each of those polynomials?

My solution was to brute force it by solving a matrix (see Finding polynomials from huge sets of points), but Java wasn't good enough to do all that math (couldn't contain huge numbers with good enough precision).

Is there a better, more elegant way to do the problem? If not, how would I brute force it?

If $p(x)$ satisfies the given conditions, then $$f(x) = xp(x)-x^2-1$$ is a polynomial of degree $d+1$ (assuming $d\geq 1$) with zeros at $x = 1,2,\ldots,99$.

Note that $f$ satisfies $f(0) = -1$, so it cannot be the polynomial that is identically zero-valued. Thus $f$ can have at most $d+1$ distinct zeros, so we must have $d\geq 98$.

If $d = 98$, then the location of zeros of $f(x)$ implies $$f(x) = k(x-1)(x-2)\cdots(x-99)$$ for some constant $k$. But since $$-1 = f(0) = k\cdot(-1)^{99}(99!),$$ we may solve for $k = \frac1{99!}$. In this case $f(100) = k\cdot(99!) = 1$, so then $$p(100) = \frac1{100} (f(100) + 100^2 + 1) = 100 + \frac2{100}.$$

If $d\geq 99$, then we have $$f(x) = \frac1{99!}(x-1)(x-2)\cdots(x-99)g(x)$$ for some (arbitrary) polynomial $g(x)$ of degree $d - 98$, normalized to $g(0) = 1$. In this case $f(100) = g(100)$, and $$p(100) = \frac1{100} (g(100) + 100^2 + 1 ) = 100 + \frac{1 + g(100)}{100}.$$

From the given condition $nP(n)=n^2+1$ for $n=1,2,\cdots,99$. So the polynomial $P^{\star}(x)=xP(x)-x^2-1$ of degree $d+1$, has 99 zeros. If $d<98$ then $P^{\star}(x)$, despite of being of degree $d+1$, would have $>d+1$ roots, and hence should be identically equal to zero for every $x$. Then $P(100)$ would be simply $\frac{P^{\star}(100)+(100^2+1)}{100}=100+\frac1{100}$.

Now if $d=98$ then we can represent $$P^{\star}(x)=(x-1)(x-2)\cdots(x-99)$$ assuming $P$ to be a monic polynomial. Then $P(100)=\frac{P^{\star}(100)+(100^2+1)}{100}=\frac{99!+10001}{100}$.

If $d>98$ then we can represent $$P^{\star}(x)=(x-1)(x-2)\cdots(x-99)g(x)$$ With $g(x)$ being a polynomial of degree $\ge1$. But then due to indeterminacy of $g(x)$ we can't calculate the exact value of $P(100)$.

• That's wrong: $P^{\star}(x)=xP(x)-x^2-1$ doesn't only have to have zeros at $x=1,2,\ldots,99$, it also must satisfy $P^{\star}(0)=0\cdot P(0)-0^2-1=-1$. – Professor Vector Dec 14 '17 at 5:34
• You can’t assume $P^*$ is monic, since it necessarily has constant term equal to $-1$. Similarly, the hypothetical case where $P^*$ is identically zero cannot actually occur. – Erick Wong Dec 14 '17 at 5:35