Maths Olympiad Prep

Library / February /52 of 62

February, 2017

Algebra Difficulty 6.2 National Olympiad Prove it United States

Problem:

A polynomial PP of degree 20152015 satisfies the equation P(n)=1n2P(n)=\frac{1}{n^{2}} for n=1,2,…,2016n=1,2, \ldots, 2016. Find ⌊2017P(2017)⌋\lfloor 2017 P(2017)\rfloor.

Solution

Solution:

Let Q(x)=x2P(x)−1Q(x)=x^{2} P(x)-1. Then Q(n)=n2P(n)−1=0Q(n)=n^{2} P(n)-1=0 for n=1,2,…,2016n=1,2, \ldots, 2016, and QQ has degree 20172017. Thus we may write
Q(x)=x2P(x)−1=(x−1)(x−2)…(x−2016)L(x) Q(x)=x^{2} P(x)-1=(x-1)(x-2) \ldots(x-2016) L(x)
where L(x)L(x) is some linear polynomial. Then Q(0)=−1=(−1)(−2)…(−2016)L(0)Q(0)=-1=(-1)(-2) \ldots(-2016) L(0), so L(0)=−12016!L(0)=-\frac{1}{2016!}.

Now note that
Q′(x)=x2P′(x)+2xP(x)=∑i=12016(x−1)…(x−(i−1))(x−(i+1))…(x−2016)L(x)+(x−1)(x−2)…(x−2016)L′(x) \begin{aligned} Q^{\prime}(x) & =x^{2} P^{\prime}(x)+2 x P(x) \\ & =\sum_{i=1}^{2016}(x-1) \ldots(x-(i-1))(x-(i+1)) \ldots(x-2016) L(x)+(x-1)(x-2) \ldots(x-2016) L^{\prime}(x) \end{aligned}
Thus
Q′(0)=0=L(0)(2016!−1+2016!−2+…+2016!−2016)+2016!L′(0) Q^{\prime}(0)=0=L(0)\left(\frac{2016!}{-1}+\frac{2016!}{-2}+\ldots+\frac{2016!}{-2016}\right)+2016!L^{\prime}(0)
whence L′(0)=L(0)(11+12+…+12016)=−H20162016!L^{\prime}(0)=L(0)\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{2016}\right)=-\frac{H_{2016}}{2016!}, where HnH_{n} denotes the nnth harmonic number.

As a result, we have L(x)=−H2016x+12016!L(x)=-\frac{H_{2016} x+1}{2016!}. Then
Q(2017)=20172P(2017)−1=2016!(−2017H2016+12016!) Q(2017)=2017^{2} P(2017)-1=2016!\left(-\frac{2017 H_{2016}+1}{2016!}\right)
which is −2017H2016−1-2017 H_{2016}-1. Thus
P(2017)=−H20162017 P(2017)=\frac{-H_{2016}}{2017}
From which we get 2017P(2017)=−H20162017 P(2017)=-H_{2016}. It remains to approximate H2016H_{2016}. We alter the well known approximation
Hn≈∫1n1xdx=log⁡x H_{n} \approx \int_{1}^{n} \frac{1}{x} d x=\log x
to
Hn≈1+12+∫3n1xdx=1+12+log⁡(2016)−log⁡(3)≈log⁡(2016)+12 H_{n} \approx 1+\frac{1}{2}+\int_{3}^{n} \frac{1}{x} d x=1+\frac{1}{2}+\log (2016)-\log (3) \approx \log (2016)+\frac{1}{2}
so that it suffices to lower bound log⁡(2016)\log (2016). Note that e3≈20e^{3} \approx 20, which is close enough for our purposes. Then e6≈400⟹e7≈1080e^{6} \approx 400 \Longrightarrow e^{7} \approx 1080, and e3≈20<25⟹e0.6≪2⟹e7.6<2016e^{3} \approx 20<2^{5} \Longrightarrow e^{0.6} \ll 2 \Longrightarrow e^{7.6}<2016, so that log⁡(2016)>7.6\log (2016)>7.6. It follows that H2016≈log⁡(2016)+0.5=7.6+0.5>8H_{2016} \approx \log (2016)+0.5=7.6+0.5>8 (of course these are loose estimates, but more than good enough for our purposes). Thus −9<2017P(2017)<−8-9<2017 P(2017)<-8, making our answer −9-9.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.