Polynomial

[Bkd]

f(x) is a ploynomial such that f(1)=3, f(2)=3, f(3)=6, f(4)=1,f(5)=4, f(6)=6, f(7)=2, f(8)=5, f(9)=0, f(10)=3, f(11)=5, f(12)=1.Find the equation of x, i.e. f(x).

[Daedalus]

f(x) is a ploynomial such that f(1)=3, f(2)=3, f(3)=6, f(4)=1,f(5)=4, f(6)=6, f(7)=2, f(8)=5, f(9)=0, f(10)=3, f(11)=5, f(12)=1.Find the equation of x, i.e. f(x).

 

This is really easy using Newton's interpolation method. I extended Newton's method to allow for increasing summations of [math]f(x)[/math] and to exponential equations too, which I demonstrated in my Fourth Challenge and allows us to derive an exponential equation that will also interpolate [math]f(x)[/math] as well as increasing products of [math]f(x)[/math]. Note: the exponential interpolation method cannot handle zeroes in the range.

 

The Process:

 

I figured out how to do this when I discovered Newton's interpolation formula my 11th grade year in high school. I didn't know about interpolation at the time. I was in Trigonometry and had learned that summations of [math]x[/math] had a polynomial that generalized the sum. It took me one year and three months to discover the equation which predicted the summations of [math]x^p[/math]. I did not have a computer and I did all of the calculation using paper and a TI-88 (I sure do love Mathematica... It has saved a lot of trees):

 

[math]F(s,\, n,\, p)=\sum_{j_{1}=1}^n \sum_{j_{2}=1}^{j_{1}} ... \sum_{x=1}^{j_{S}} (x^p)=\sum_{j=0}^p \left((-1)^{j+p} \left(\sum_{k=0}^j \frac{k^p \, \left \langle -j \right \rangle_{j-k}}{(j-k)!}\right)\left(\frac{\left \langle n \right \rangle_{j+s}}{(j+s)!} \right)\right)[/math]

 

Where [math]s[/math] represents the recursion level of the summation (when [math]s=0[/math] we get the original sequence and when [math]s=1[/math] we get the first summation of the sequence and so on), and we sum the function, [math]x^p[/math], from [math]0[/math] to [math]n[/math] where [math]p[/math] is the power.

 

The process, which involved recursively taking the deltas of the number sequences and applying the rising factorial or Pochhammer function, allowed me to derive the exponential version by recursively dividing instead of doing a subtraction. This is demonstrated below (note: I replaced the Pochhammer function with a product series operator for those that are not familiar with the rising factorial):

 

Newton's Interpolation:

 

Recursively take the deltas of each sequence:

 

[math] \begin{matrix} & & & y_4 - 3\, y_3 + 3\, y_2 - y_1\\ & & y_3 - 2\, y_2 + y_1 & y_4 - 2\, y_3 + y_2\\ & y_2 - y_1 & y_3 - y_2 & y_4 - y_3 \\ y_1 & y_2 & y_3 & y_4 \end{matrix} [/math]

 

We are only interested in the results at the top of each column. Also, we can see that each result is an alternating sum of the original sequence with coefficients that are pascal numbers. Next, we use each result with the rising factorial and standard factorial as follows:

 

[math]\left(y_1\right)\frac{1}{0!}\ -\ \left(y_2 - y_1\right)\frac{(1-x)}{1!}\ +\ \left(y_3 - 2\, y_2 + y_1\right)\frac{(1-x)(2-x)}{2!}\ -\ \left(y_4 - 3\, y_3 + 3\, y_2 - y_1\right)\frac{(1-x)(2-x)(3-x)}{3!}\ +\ \text{etc...}[/math]

 

The formula which defines this process is as defined below (note: I have expanded the formula to include recursively summing the sequence such that when [math]s=0[/math] we get the original sequence and when [math]s=1[/math] we get the first summation of the sequence and so on):

 

[math]F(x, \, s,\, n) = \sum_{i=0}^{n-1}\left( \sum_{j=0}^{i}\left(f(j)\frac{(-1)^{j}\ i!}{j!\ (i-j)!}\right) \frac{(-1)^{s}}{(i+s)!} \prod_{k=1}^{i+s}\left(k-s-x\right)\right)[/math]

 

Where [math]x[/math] is the variable, [math]s[/math] is the summation as explained above, and we sum from [math]0[/math] to [math]n-1[/math]. We can start from any number by modifying [math]f(j)[/math] to include a starting index, [math]f(j+start)[/math].

 

Daedalus' Exponential Interpolation:

 

We must do the same thing as above except we will divide the numbers of the sequence:

 

[math] \begin{matrix} & & & y_4^1 \times y_3^{-3} \times y_2^{3} \times y_1^{-1}\\ & & y_3^1 \times y_2^{-2} \times y_1^1 & y_4^1 \times y_3^{-2} \times y_2^1\\ & y_2^1 \times y_1^{-1} & y_3^1 \times y_2^{-1} & y_4^1 \times y_3^{-1} \\ y_1 & y_2 & y_3 & y_4 \end{matrix} [/math]

 

The next part is also similar except additions become multiplications, subtractions become division, and multiplication becomes exponents:

 

[math]\left(y_1\right)^{\frac{1}{0!}}\ \times\ \left(y_2^1 \times y_1^{-1}\right)^{-\frac{(1-x)}{1!}}\ \times \ \left(y_3^1 \times y_2^{-2} \times y_1^1\right)^{\frac{(1-x)(2-x)}{2!}}\ \times \ \left(y_4^1 \times y_3^{-3} \times y_2^{3} \times y_1^{-1}\right)^{-\frac{(1-x)(2-x)(3-x)}{3!}}\ \times \ \text{etc...}[/math]

 

The following formula defines the above process such that when [math]p=0[/math] we get the original sequence and when [math]p=1[/math] we get the first product of the sequence and so on:

 

[math]F(x, \, p,\, n) = \prod_{i=0}^{n-1}\left( \prod_{j=0}^{i}\left(f(j)^{\frac{(-1)^{j}\, i!}{j!\, (i-j)!}}\right)^{ \frac{(-1)^{p}}{(i+p)!} \displaystyle \prod_{k=1}^{i+p}\left(k-p-x\right)}\right)[/math]

 

Where [math]x[/math] is the variable, [math]p[/math] is the recursion level of the product as explained above, and we multiply the outputs from [math]0[/math] to [math]n-1[/math]. We can start from any number by modifying [math]f(j)[/math] to include a starting index, [math]f(j+start)[/math].

 

This method can be applied to any operator that obeys the associative law (which is why it only works for summations and products). Please forgive any grammar errors in this post. I broke a tooth over thanksgiving and it is causing me a tremendous amount of pain. It's 3:00 am and I have a dentist appointment today. So... I kinda rushed this post. I will correct any issues tomorrow as long as the edit timer has not expired.

The polynomial the interpolates [math]f(x)[/math] is

 

[math]\frac{359}{6652800}x^{11}-\frac{977}{259200}x^{10}+\frac{42001}{362880}x^{9}-\frac{17761}{8640}x^{8}+\frac{14137327}{604800}x^{7}-\frac{15371867}{86400}x^{6}+[/math]

 

[math]\frac{111321821}{120960}x^{5}-\frac{2605751}{810}x^{4}+\frac{3355619803}{453600}x^{3}-\frac{2379611}{225}x^{2}+\frac{58055651}{6930}x-2743[/math]

 

I attached a Mathematica 7 file that shows how I derived the above polynomial and proves that it interpolates the specified range.

Polynomial.zip

Edited April 6, 2017 by Daedalus

[wtf]

http://www.dcode.fr/lagrange-interpolating-polynomial

[Bkd]

Could it be expressed in trigonometric function? Actually I expect it in a more simplified form.

If we plot the points (1,3), (2,3), (3,6), (4,1), (5,4), (6,6), (7,2), (8,5), (9,0), (10,3), (11,5), (12,1) on graph paper, we get a sin or cos like curve (nearly). Plz help.

[Bkd]

@Daedalus sir,

Thank you sir for helping.

But there is a mistake in the f(x) which you have solved. It gives the nearly correct value for f(1)=2.9.... , f(2)=2.9...., but from f(3) to f(12) it gives the value so absurd.

 

Could it be expressed in trigonometric function? Actually I expect it in a more simplified form.

If we plot the points (1,3), (2,3), (3,6), (4,1), (5,4), (6,6), (7,2), (8,5), (9,0), (10,3), (11,5), (12,1) on graph paper, we get a sin or cos like curve (nearly). Plz help.