2018 polynomial

Let's consider the polynomial $x^2 P(x) - 1$ . For all $x=1,2,...,2016$ this polynomial evaluates to zero. Therefore we have 2016 roots and because this polynomial is of degree 2017 we may write: $x^2 P(x) - 1 = (x-1)(x-2)...(x-2016) (ax + b)$ . I will solve this problem by finding what $a$ and $b$ are. Let's start with $b$ . Evaluate both sides for $x=0$ to obtain $-1 = (2016)!b$ so $b = \frac{-1}{2016!}$ .

To find what $a$ is, notice that the polynomial we are studying has an interesting property: It has no $x$ term. This is because the polynomial $x^2 P(x)$ has only terms of degree larger than 1. But on the right-hand side, we can spot what the $x$ term coefficient is. First, let's compute the $x$ and constant term of the polynomial $(x-1)(x-2)...(x-2016)$ . The constant term will be just the product of all those constants, $2016!$ . but for the $x$ term we have to do a little work:

The easiest way of conveying this is that if we say that $c_n$ is the $x$ term's coefficient of the polynomial $(x-1)...(x-n)$ then we have the recurrence relation $c_1 = 1, c_n = (-1)^{n+1} (n |a_{n-1}| + (n-1)!$ ) and the solution to this recurrence relation is $c_n = (-1)^{n+1}n! H_n$ . (This may be discovered through more elementary but longer calculations). Therefore the coefficient of the $x$ term is $-2016! H_{2016}$ .

Therefore the $x$ term of the entire polynomial $(x-1)...(x-2016)(ax + b)$ will be $2016!a - 2016! H_{2016}b$ but we know this coefficient has to be 0 so we have the equation $2016!a - 2016! H_{2016}b = 0$ . We already know what $b$ is so solving for $a$ we get $a= -\frac{H_{2016}}{2016!}$ .

Now, there are many ways to conclude as we now have an explicit product representation of our polynomial, but the path I initially took was: Evaluate the expression $x^2 P(x) - 1 = (x-1)(x-2)...(x-2016) (ax + b)$ for $x=2017$ to obtain $2017^2 P(2017) - 1 = 2016! (2017a - \frac{1}{2016!})$ . We can reduce this to simply $2017P(2017) = 2016!a = -H_{2016}$ .

Now, use any method you know for approximating the Harmonic numbers to get a good enough approximation, $8.18$ is actually enough and the floor of $-8.18$ is $-9$ .

My solution (using Lagrange Interpolation) :

Lemma: $\quad$ For any positive integer n,we have $\displaystyle\large \sum _{k=1}^{n} \frac{1}{k}$ $\displaystyle\large =\sum _{k=1}^{n} \Big((-1)^{k-1} \tbinom {n}{k} \cdot \frac{1}{k}\Big )$

Proof of lemma by induction

Case n=1 is obvious.

Assume that the statement is true for n=k, i.e. $\displaystyle\large \sum _{i=1}^{k} \frac{1}{i}$ $\displaystyle\large =\sum _{i=1}^{k} \Big((-1)^{i-1} \tbinom {k}{i} \cdot \frac{1}{i}\Big )$ .

When $n=k+1$ ,use the assumption to get

$\displaystyle\large \sum _{i=1}^{k+1} \frac{1}{i}$ $\displaystyle\large =\sum _{i=1}^{k} \Big((-1)^{i-1} \tbinom {k}{i} \cdot \frac{1}{i}\Big )$ $\large +\frac{1}{k+1}$

$\displaystyle\large =\sum _{i=1}^{k} \Big((-1)^{i-1} \Big( \tbinom {k+1}{i}-\tbinom {k}{i-1}\Big ) \cdot \frac{1}{i}\Big )$ $\large +\frac{1}{k+1}$

$\displaystyle\large =\sum _{i=1}^{k+1} \Big((-1)^{i-1} \tbinom {k+1}{i} \cdot \frac{1}{i}\Big ) -\sum _{i=1}^{k} \Big((-1)^{i-1} \tbinom {k}{i-1} \cdot \frac{1}{i}\Big )+\frac{1-(-1)^{k}}{k+1}$ .

Now we only need to show that $\displaystyle\large \sum _{i=1}^{k} \Big((-1)^{i-1} \tbinom {k}{i-1} \cdot \frac{1}{i}\Big )=\frac{1-(-1)^{k}}{k+1}$ .

Apply the identity $\tbinom{k+1}{i}=\frac{k+1}{i}\tbinom{k}{i-1}$ to get

$\displaystyle\large \sum _{i=1}^{k} \Big((-1)^{i-1} \tbinom {k}{i-1} \cdot \frac{1}{i}\Big )= \displaystyle\large \sum _{i=1}^{k} \Big((-1)^{i-1} \tbinom {k+1}{i} \cdot \frac{1}{k+1}\Big)$

$\displaystyle\large=\frac{\displaystyle\large -\sum _{i=0}^{k+1}\tbinom {k+1}{i} (-1)^{i}-(-1)^{k}+1}{k+1}$ ( Using Binomial Theorem )

$\displaystyle\large=\frac{1-(-1)^{k}}{k+1}$ . $\quad$ $\square$

Come back. By Lagrange Interpolation,

$\large P(x)= \frac{1}{1^{2}}\cdot \frac{(x-2)(x-3)\cdots (x-2016)}{(1-2)(1-3)\cdots (1-2016)} + \frac{1}{2^{2}}\cdot \frac{(x-1)(x-3)\cdots (x-2016)}{(2-1)(2-3)\cdots (2-2016)} + \cdots + \frac{1}{2016^{2}}\cdot \frac{(x-1)(x-2)\cdots (x-2015)}{(2016-1)(2016-2)\cdots (2016-2015)}$ .

Thus,

$\large 2017P(2017)= \frac{1}{1^{2}}\cdot \frac{2017!\div 2016}{(-1)^{2015}\cdot 0!\cdot 2015!} + \frac{1}{2^{2}}\cdot \frac{2017!\div 2015}{(-1)^{2014}\cdot 1!\cdot 2014!} + \frac{1}{3^{2}}\cdot \frac{2017!\div 2014}{(-1)^{2013}\cdot 2!\cdot 2013!} + \cdots + \frac{1}{2016^{2}}\cdot \frac{2017!\div 1}{(-1)^{0}\cdot 2015!\cdot 0!}$

$\large =\frac{1}{1}\cdot \frac{2017!}{(-1)^{2015}\cdot 1!\cdot 2016!} + \frac{1}{2}\cdot \frac{2017!}{(-1)^{2014}\cdot 2!\cdot 2015!} + \frac{1}{3}\cdot \frac{2017!}{(-1)^{2013}\cdot 3!\cdot 2014!} + \cdots + \frac{1}{2016}\cdot \frac{2017!}{(-1)^{0}\cdot 2016!\cdot 1!}$

$\displaystyle\large =\sum _{k=1}^{2016} \Big((-1)^{k} \tbinom {2017}{k} \cdot \frac{1}{k}\Big )$

$\displaystyle\large =\frac{1}{2017}-\sum _{k=1}^{2017} \Big((-1)^{k-1} \tbinom {2017}{k} \cdot \frac{1}{k}\Big )$

$\displaystyle\large =\frac{1}{2017}-\sum _{k=1}^{2017} \frac{1}{k}$ ( Using the Lemma. )

$\displaystyle\large = -\sum _{k=1}^{2016} \frac{1}{k}\approx -8.186334289$ ,so the answer is $\boxed{-9}$ . $\quad$ $\blacksquare$