28 Jan '06 00:30

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)?

- Joined
- 29 Nov '02
- Moves
- 17317

Elsewhere- Joined
- 25 Oct '02
- Moves
- 20443

Out of my mind29 Jan '06 21:46

Let's see...I don't notice the trick, but Lagrange polynomials should work.*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)?**

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- Joined
- 29 Nov '02
- Moves
- 17317

Elsewhere29 Jan '06 23:43

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 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- Joined
- 11 Nov '05
- Moves
- 43938

30 Jan '06 11:33

I don't see the trick so I solve it anyway...*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)?**

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.- Joined
- 01 May '05
- Moves
- 390

30 Jan '06 14:19

But he said that P(n)=n/(n+1)*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?

*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.- Joined
- 25 Oct '02
- Moves
- 20443

Out of my mind30 Jan '06 23:11

Well, a 2000 degree polynomial is completely defined by 2001 points.*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.

(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.- Joined
- 23 Aug '04
- Moves
- 24791

tinyurl.com/y2c6j2t301 Feb '06 01:01

We have an infinite number of points here, correct? Or is there an unstated "integers only" rule about what n can be?*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.

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?- Joined
- 29 Nov '02
- Moves
- 17317

Elsewhere02 Feb '06 11:35

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.*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?

There is no rounding.- Joined
- 17 Mar '04
- Moves
- 17524

Thieve's Guild03 Feb '06 17:432 edits

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)*Originally posted by royalchicken*

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

ðŸ™„- Joined
- 29 Nov '02
- Moves
- 17317

Elsewhere03 Feb '06 18:07

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

ðŸ™„- Joined
- 14 Feb '04
- Moves
- 28719

False berry03 Feb '06 18:52

Wow, you really are a psychopath. Nice job!*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

ðŸ™„- Joined
- 25 Oct '02
- Moves
- 20443

Out of my mind