29 Jan 06
Originally posted by royalchickenLet's see...I don't notice the trick, but Lagrange polynomials should work.
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)?
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
29 Jan 06
Originally posted by TheMaster37Actually, 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.
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
30 Jan 06
Originally posted by royalchickenI don't see the trick so I solve it anyway...
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)?
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.
30 Jan 06
Originally posted by FabianFnasBut 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.
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?
Again. it's just what I assume.
30 Jan 06
Originally posted by fetofsWell, a 2000 degree polynomial is completely defined by 2001 points.
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.
(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.
01 Feb 06
Originally posted by TheMaster37We have an infinite number of points here, correct? Or is there an unstated "integers only" rule about what n can be?
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.
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?
02 Feb 06
Originally posted by AThousandYoungTo 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.
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?
There is no rounding.
03 Feb 06
2 edits
Originally posted by royalchickenLet 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)
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)?
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
🙄
03 Feb 06
Originally posted by psychopath42Nicely done!
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
🙄
03 Feb 06
Originally posted by psychopath42Wow, you really are a psychopath. Nice job!
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
🙄