A polynomial $P$ of degree 2015 satisfies the equation $P(n) = \dfrac { 1 }{ { n }^{ 2 } }$ for $n = 1, 2, . . . , 2016$ . Find $\left\lfloor 2017P(2017) \right\rfloor$ .

**
Notation:
**
$\lfloor \cdot \rfloor$
denotes the
floor function
.

The answer is -9.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

Same solution....but can i proceed with lagrange interpolation??

rajdeep brahma
- 3 years, 4 months ago

Log in to reply

Well, Lagrange interpolation would give the polynomial as you have 2016 points for a 2015 degree polynomial, but I am not sure how you could get to the problem's solution without an inhuman amount of computation.

Leonel Castillo
- 3 years, 4 months ago

Log in to reply

Yeah ok...got it...then it is better to avoid that...thanks.

rajdeep brahma
- 3 years, 4 months ago

Hi,Leonel Castillo. I have done the ' inhuman amount of computation ' in my solution.Ah,I'm really exhausted when I finish typing. Of course ,I prefer your solution...

Haosen Chen
- 3 years, 2 months ago

Is there a way to approximate H_2016 without a calculator?

Alexander Xue
- 3 years, 4 months ago

Log in to reply

Not really, unless you have a log table. H_2016 is approximately equal to log(2016) + 0.577 so that is how you would quickly compute it with a basic calculator. Beyond that, no idea.

Leonel Castillo
- 3 years, 4 months ago

Log in to reply

Oh that's interesting, why is it approximately ln + 0.577 (I think you mean ln(2016) not log)?

Alexander Xue
- 3 years, 4 months ago

Log in to reply

@Alexander Xue
–
Well, it is a theorem that the limit as n goes to infinity of H
*
n - ln(n) is exactly the Euler-Masceroni constant, of which I just memorized the digits 0.577. That is why you can approximate H
*
n = ln(n) + 0.577. This is especially true for really big n (like 2016) because the error term for this approximation is approximately 1/n, so you will find in analytic number theory textbooks that H_n = log(n) + 0.577... + O(1/n).

Leonel Castillo
- 3 years, 4 months ago

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$

1 Helpful
0 Interesting
0 Brilliant
0 Confused

@Haosen Chen , I Am not very good at langrange interpolation polynomial. Can you help me to understand it?

Priyanshu Mishra
- 3 years, 2 months ago

Hi,Priyanshu Mishra.

Since P(x) is a polynomial of degree 2015 ,and 2016 distinct points on the graph of y=P(x) are given, P(x) is uniquely determined.

To figure out what P(x) exactly is, you can use Lagrange Interpolation.After that you'll get a long algebraic expression of P(2017) and enjoy the 'compution'.

see here :

1.https://brilliant.org/wiki/lagrange-interpolation/

2.http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html

Haosen Chen
- 3 years, 2 months ago

×

Problem Loading...

Note Loading...

Set Loading...

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