Inspired by Comrade Pi Han Goh
Let f ( x ) be a quintic ( 5 th degree) polynomial with f ( n ) = 2 n for all integers 0 ≤ n ≤ 5 . Find f ( 1 1 ) .
The answer is 1024.
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.
4 solutions
Yes, this is the systematic way of doing it! (+1)
Did the same ! I fear that we could not make polynomial f (x) (using interpolation) with the given conditions on x.
Otto sir and chew sir , both your methods are also nice ! time savers :)
We claim that f ( x ) = ∑ k = 0 5 ( k x ) . Indeed, if 0 ≤ n ≤ 5 , then f ( n ) = ∑ k = 0 5 ( k n ) = ∑ k = 0 n ( k n ) = 2 n as required. Now f ( 1 1 ) = ∑ k = 0 5 ( k 1 1 ) = 2 1 ∑ k = 0 1 1 ( k 1 1 ) = 2 1 × 2 1 1 = 2 1 0 = 1 0 2 4
Moderator note:
Great way to identify the polynomial which approximates this value. Makes it easier than the other interpolation formats.
Oh! I see. Wunderbar!
I also tried Langrages Interpolation method , but I got stuck in between ....and finally I did it by Method of diff.
Log in to reply
I'm no expert on computational complexity, but it does not appear that Lagrange Interpolation is any shorter in this case ;)
Log in to reply
If the test values are consecutive, as here, the Method of Differences is probably faster of the two methods, and simple to implement in Excel (or similar). Where Lagrangian Interpolation scores is when the test values are not consecutive.
Log in to reply
@Mark Hennings – And where does my method fit in, using binomial coefficients?
Log in to reply
@Otto Bretscher – I was commenting on the general approach. Given this very specific case, where there is a neat solution, demonstrating that the answer works is always the simplest and quickest. That leaves open the question of how to arrive at said neat solution,
Log in to reply
@Mark Hennings – For me, that's what doing math is all about, particularly on a "fun" site like this: arriving at short, elegant, neat solutions rather than applying known algorithms. We are mathematicians, after all, not book keepers ;)
The binomial approach works here and here ... whenever we are fitting a polynomial to an exponential function.
Log in to reply
@Otto Bretscher – Otto, I call your approach polynomial interpolation by remainder factor theorem . The trick is to find the polynomial which matches the values exactly, and it's not always obvious how to do this (see the 3rd section)
Any thoughts on other cases?
Log in to reply
@Calvin Lin – Yes, Calvin, this is great stuff! Thank you! I had no idea this method even has a name ;)
I will take a closer look when I have some time.
In a way, I prefer to do these problems without prefabricated methods, just "doing a little thinking" on a case-by-case basis... but these guide lines are a good thing for people who plan to take part in math competitions.
Frankly, I solve all these polynomial problems by cheating, using matrix operations on Excel spreadsheet. Because with known X and Y , it is a linear system. A X = Y , ⇒ A = X − 1 Y and I got A .
Log in to reply
I was trained an engineer, who just solves the problem, not a mathematician.
Can Langrange interpolation be used here ?
Log in to reply
Yes, Comrade Cheong is using Lagrange Interpolation. Both finite differences and Lagrange interpolation are solid, systematic methods, but, as Akshat says, they are rather "long" ;)
Since k = 0 , = i ∏ 5 ( x − k ) { = 0 = 0 if x = i if x = i , where i = 0 , 1 , 2 , 3 , 4 , 5 , we can write f ( x ) as follows.
f ( x ) ⇒ f ( 1 1 ) = − 1 2 0 2 0 k = 1 ∏ 5 ( x − k ) + 2 4 2 1 k = 0 , = 1 ∏ 5 ( x − k ) − 1 2 2 2 k = 0 , = 2 ∏ 5 ( x − k ) + 1 2 2 3 k = 0 , = 3 ∏ 5 ( x − k ) − 2 4 2 4 k = 0 , = 4 ∏ 5 ( x − k ) − 1 2 0 2 5 k = 0 ∏ 4 ( x − k ) = − 1 2 0 1 k = 1 ∏ 5 ( x − k ) + 1 2 1 k = 0 , = 1 ∏ 5 ( x − k ) − 3 1 k = 0 , = 2 ∏ 5 ( x − k ) + 3 2 k = 0 , = 3 ∏ 5 ( x − k ) − 3 2 k = 0 , = 4 ∏ 5 ( x − k ) − 1 5 4 k = 0 ∏ 4 ( x − k ) = − 1 2 0 ˙ 1 1 1 1 ˙ 1 0 ˙ 9 ˙ 8 ˙ 7 ˙ 6 + 1 2 ˙ 1 0 1 1 ˙ 1 0 ˙ 9 ˙ 8 ˙ 7 ˙ 6 − 3 ˙ 9 1 1 ˙ 1 0 ˙ 9 ˙ 8 ˙ 7 ˙ 6 + 3 ˙ 8 2 ˙ 1 1 ˙ 1 0 ˙ 9 ˙ 8 ˙ 7 ˙ 6 − 3 ˙ 7 2 ˙ 1 1 ˙ 1 0 ˙ 9 ˙ 8 ˙ 7 ˙ 6 + 1 5 ˙ 6 4 ˙ 1 1 ˙ 1 0 ˙ 9 ˙ 8 ˙ 7 ˙ 6 = − 2 5 2 + 2 7 7 2 − 1 2 3 2 0 + 2 7 7 2 0 − 3 1 6 8 0 + 1 4 7 8 4 = 1 0 2 4
Yes, another systematic approach, Comrade! (+1)
Same method.
Can u explain the method please?
Log in to reply
It is called Langrange interpolation. Check out the link .
Consider the product P 0 = ( x − 1 ) ( x − 2 ) ( x − 3 ) ( x − 4 ) ( x − 5 ) .
P 0 = { 0 − 5 ! = 1 2 0 when x = 1 , 2 , 3 , 4 , 5 when x = 0
Now, for f 0 = 2 0 , we can write f 0 = − 1 2 0 2 0 P 0 = − 1 2 0 2 0 ∏ k = 1 5 ( x − k ) . We can write f ( x ) as follows:
f ( x ) = f 0 + f 1 + f 2 + f 3 + f 4 + f 5 = − 1 2 0 2 0 P 0 + 2 4 2 1 P 1 − 1 2 2 2 P 2 + 1 2 2 3 P 3 − 2 4 2 4 P 4 − 1 2 0 2 5 P 5 = − 1 2 0 2 0 k = 1 ∏ 5 ( x − k ) + 2 4 2 1 k = 0 , = 1 ∏ 5 ( x − k ) − 1 2 2 2 k = 0 , = 2 ∏ 5 ( x − k ) + 1 2 2 3 k = 0 , = 3 ∏ 5 ( x − k ) − 2 4 2 4 k = 0 , = 4 ∏ 5 ( x − k ) − 1 2 0 2 5 k = 0 ∏ 4 ( x − k )
Found that the function is f ( n ) = x 5 / 1 2 0 − x 4 / 2 4 + 5 x 3 / 2 4 + x 2 / 2 4 + 4 7 x / 6 0 + 1 through solving a system of equations
This would have been very long !
How did you do that?
Man you have a lot of patience!! How did you solved the system of equations?
I used a rather long method, the Method of Differences,
n n 0 1 2 3 4 5 6 7 8 9 1 0 1 1 f ( n ) 1 2 4 8 1 6 3 2 6 3 1 2 0 2 1 9 3 8 2 6 3 8 1 0 2 4 D 1 ( n ) 1 2 4 8 1 6 3 1 5 7 9 9 1 6 3 2 5 6 3 8 6 D 2 ( n ) 1 2 4 8 1 5 2 6 4 2 6 4 9 3 1 3 0 D 3 ( n ) 1 2 4 7 1 1 1 6 2 2 2 9 3 7 D 4 ( n ) 1 2 3 4 5 6 7 8 D 5 ( n ) 1 1 1 1 1 1 1