Simple if you spot the trick

Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?

Originally posted by royalchicken
Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?

Let's see...I don't notice the trick, but Lagrange polynomials should work.

P is completely define by the 2001 points given, wich means P(2001) is a fixed value.

To determine that value you need patience, a computer, or the trick.

Since I have none of the three mentioned above, I'll leave this to you to demonstrate :p

Originally posted by TheMaster37
Let's see...I don't notice the trick, but Lagrange polynomials should work.

P is completely define by the 2001 points given, wich means P(2001) is a fixed value.

To determine that value you need patience, a computer, or the trick.

Since I have none of the three mentioned above, I'll leave this to you to demonstrate :p

Actually, someone asked me this, and I did not spot the trick, so I wrote a little program to do it (really just to invert a matrix). I was hoping RHP could think of something cleverer.

Originally posted by royalchicken
Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?

I don't see the trick so I solve it anyway...

If P(n) = n/(n+1)
then P(2001) = 2001/2002 = 0,9 995004 995004 995004 ... right?

Is the trick to realize that n/(n+1) isn't a polynomial so you have to find a Taylor-approximation or someting? But the answer should be same, perhaps only with a residual included.

Originally posted by FabianFnas
I don't see the trick so I solve it anyway...

If P(n) = n/(n+1)
then P(2001) = 2001/2002 = 0,9 995004 995004 995004 ... right?

But he said that P(n)=n/(n+1) for n between 0 and 2000 so I assume that rule is not valid for P(2001), and there is another polynomial that gives n/n+1 for these n and maybe deviates at n=2001. Otherwise, this would be pretty simple, even I can divide two numbers.

Again. it's just what I assume.

Originally posted by fetofs
But he said that P(n)=n/(n+1) for n between 0 and 2000 so I assume that rule is not valid for P(2001), and there is another polynomial that gives n/n+1 for these n and maybe deviates at n=2001. Otherwise, this would be pretty simple, even I can divide two numbers.

Again. it's just what I assume.

Well, a 2000 degree polynomial is completely defined by 2001 points.

(as a line is defined by two points).

F(x) = x/(x+1) is not a polynomial, that's easily proven.

With that P(2001) will most likely NOT be equal to 2000/2001, as the graph of P will increase or decrease rapidly after 2000.

Originally posted by TheMaster37
Well, a 2000 degree polynomial is completely defined by 2001 points.

(as a line is defined by two points).

F(x) = x/(x+1) is not a polynomial, that's easily proven.

With that P(2001) will most likely NOT be equal to 2000/2001, as the graph of P will increase or decrease rapidly after 2000.

We have an infinite number of points here, correct? Or is there an unstated "integers only" rule about what n can be?

The graph is going to be the graph of y = x/(x+1) until maybe after x=2000. Can one have a polynomial of finite degree be so perfectly smooth? Are we assuming that P(n) = n/(n+1) exactly or is there some rounding assumed?

Originally posted by AThousandYoung
We have an infinite number of points here, correct? Or is there an unstated "integers only" rule about what n can be?

The graph is going to be the graph of y = x/(x+1) until maybe after x=2000. Can one have a polynomial of finite degree be so perfectly smooth? Are we assuming that P(n) = n/(n+1) exactly or is there some rounding assumed?

To clarify: P is a polynomial that takes the values stated at integers between 0 and 2000 inclusive, and may take other values at non-integral points.

There is no rounding.

Originally posted by royalchicken
Let P be a polynomial of degree 2000 with P(n) = n/(n+1) for n between 0 and 2000 inclusive. What is P(2001)?

Let f(x) = a_1*x + a_2*x(x-1) + a_3*x(x-1)(x-2) + ... + a_2000*x(x-1)(x-2)...(x-1999)
where
a_k = (-1)^(k+1)/(k+1)!

Lemma: f(x) = P(x)

Proof of lemma:
It suffices to show that f(n) = n/(n+1) for all integers n=0,...,2000 inclusive.
For n=0:
f(0) = 0 is obvious

For n=1,...,2000:
f(n) = a_1*n + a_2*n(n-1) + a_3*n(n-1)(n-2) + ... + a_n*n(n-1)(n-2)...(2)(1)
= n/2! - n(n-1)/3! + n(n-1)(n-2)/4! - ... +/- n(n-1)(n-2)...(2)(1)/(n+1)!
= 1/(n+1) * [ (n+1)n/2! - (n+1)n(n-1)/3! + (n+1)n(n-1)(n-2)/4! - ... +/- (n+1)n(n-1)(n-2)...(2)(1)/(n+1)! ]
= 1/(n+1) * [ C(n+1,2) - C(n+1,3) + C(n+1,4) - ... +/- C(n+1,n+1) ]
= 1/(n+1) * [ - C(n+1,0) + C(n+1,1) ]
= 1/(n+1) * [ -1 + n + 1 ]
= n/(n+1)

Note that the combinatorial formula
sum( (-1)^k*C(n+1,k) )_{k=0}^{n+1} = 0
was used.

Corollary: f(2001) = 1000/1001

f(2001) = a_1*2001 + a_2*(2001)(2000) + a_3*(2001)(2000)(1999) + ... + a_2000*(2001)(2000)(1999)...(3)(2)
= 2001/2! - (2001)(2000)/3! + (2001)(2000)(1999)/4! - ... - (2001)(2000)(1999)...(3)(2)/2001!
= 1/2002 * [ (2002)(2001)/2! - (2002)(2001)(2000)/3! + (2002)(2001)(2000)(1999)/4! - ... - (2002)(2001)(2000)(1999)...(2)/2001! ]
= 1/2002 * [ C(2002,2) - C(2002,3) + C(2002,4) - ... - C(2002,2001) ]
= 1/2002 * [ - C(2002,0) + C(2002,1) - C(2002,2002) ]
= 1/2002 * [ -1 + 2002 - 1 ]
= 1000/1001

🙄

Originally posted by psychopath42
Let f(x) = a_1*x + a_2*x(x-1) + a_3*x(x-1)(x-2) + ... + a_2000*x(x-1)(x-2)...(x-1999)
where
a_k = (-1)^(k+1)/(k+1)!

Lemma: f(x) = P(x)

Proof of lemma:
It suffices to show that f(n) = n/(n+1) for all integers n=0,...,2000 inclusive.
For n=0:
f(0) = 0 is obvious

For n=1,...,2000:
f(n) = a_1*n + a_2*n(n-1) + a_3*n(n-1)(n-2) + ... + a_n*n(n-1 ...[text shortened]... 02 * [ - C(2002,0) + C(2002,1) - C(2002,2002) ]
= 1/2002 * [ -1 + 2002 - 1 ]
= 1000/1001

🙄

Nicely done!

Originally posted by psychopath42
Let f(x) = a_1*x + a_2*x(x-1) + a_3*x(x-1)(x-2) + ... + a_2000*x(x-1)(x-2)...(x-1999)
where
a_k = (-1)^(k+1)/(k+1)!

Lemma: f(x) = P(x)

Proof of lemma:
It suffices to show that f(n) = n/(n+1) for all integers n=0,...,2000 inclusive.
For n=0:
f(0) = 0 is obvious

For n=1,...,2000:
f(n) = a_1*n + a_2*n(n-1) + a_3*n(n-1)(n-2) + ... + a_n*n(n-1 ...[text shortened]... 02 * [ - C(2002,0) + C(2002,1) - C(2002,2002) ]
= 1/2002 * [ -1 + 2002 - 1 ]
= 1000/1001

🙄

Wow, you really are a psychopath. Nice job!

Aha, so that's the trick! Thanks for helping us out of our misery 🙂