Is it possible to have a rule which generates: 2, 4, 6, 8, 10, 12, 14, 16, -23?

Question

This is on Lagrange Interpolations . . .

Is it possible to have a rule which generates the sequence: 2, 4, 6, 8, 10, 12, 14, 16, -23?

The hint that he gave us is to use Summation Products, the only thing I can come up with is $\sum_{i=1}^{8}{2}$. I cannot come up with any formula for a Summation Product that would produce something like a 2 + 2 + 2 + . . .

I know how to use the equation for Lagrange Interpolation, but I cannot see how to apply it here . . .

Answer 1

[This is a direct approach, avoiding Lagrange inteprolation, simply because it is easier.]

Sure, for $n=1,2,\dots,8$, your formula is $2n$. So you want a formula:

$$f(n)=2n + g(n)$$

Where $g(n)$ is some formula with $0=g(1)=g(2)=g(3)=\dots=g(8)$ and $g(9) = -41$. The simplest such $g$ satisfying the zero condition are of the form:

$$g(n)=A(n-1)(n-2)\dots(n-8)$$

for some constant $A$. Choose $A$ so that $g(9)=-41$.

This is a very simple example of the method of finite differences to interpolate a finite sequence as a polynomial. In general, we we have a sequence:

$$a=(a_1,a_2,a_3,\dots,a_n)$$ Then we can define the simple difference:

$$\Delta a = (a_2-a_1,a_3-a_2,\dots,a_{n}-a_{n-1})$$

And we can repeat, giving $\Delta^2a$, $\Delta^3 a$, etc. We also define $\Delta^0 a= a$.

then we can write a polynomial. Let $d_i$ be the first element of the seequence $\Delta^i a$. Then we write the polynomial:

$$p(x) = \sum_{i=0}^n d_i\frac{(x-1)\dots(x-i)}{i!}$$

where, in the case that $i=0$, the numerate and denominator are taken to be $1$.

It turns out that $p(i)=a_i$.

Now, our above sequence $a=(2,4,6,8,10,12,14,16,-23)$ has:

$$\begin{align}\Delta^1 a &= (2,2,2,2,2,2,2,-41)\\ \Delta^2 a &= (0,0,0,0,0,0,-43)\\ \Delta^3 a &= (0,0,0,0,0,-43)\\ \Delta^4 a &= (0,0,0,0,-43)\\ \Delta^5 a &= (0,0,0,-43)\\ \Delta^6 a &= (0,0,-43)\\ \Delta^7 a &= (0,-43)\\ \Delta^8 a &= (-43)\\ \end{align}$$

So $d_0=2$, $d_1=2$ and $d_2=d_3=d_4=d_5=d_6=d_7=0$ and finally $d_8=-43$.

It's the fact that these $d_i$ are mostly zero that makes this example so easy.

This means that $$p(x) = 2 + 2(x-1) - 43\frac{(x-1)(x-2)\dots(x-8)}{8!}$$

I forget what this technique is called - I always heard it called "finite differences," I think, but it might have a more formal name.

Answer 2

To use Lagrange interpolation, note that you have a set of polynomials $L_1(x)$ through $L_9(x)$ such that $L_i(i)=1, L_i(j)=0$ for $i \neq j$ Then the formula you want is $2L_1(x)+4L_2(x)+\ldots-23L_9(x)$ Since this is an eighth degree polynomial that agrees with Thomas Andrews' solution at nine points, it is the same.

Answer 3

Thomas Andrews's solution is the best one, but you may also consider this simplistic but longer and bulky solution:

$$ \begin{array}{lccr} \\ f(x) & = & & a_1\times(-1)^{1-1}\times\frac{1}{9!}(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9) \\ & & + & a_2\times(-1)^{2-1}\times\frac{2}{9!}(x-1)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9) \\ & & + & a_3\times(-1)^{3-1}\times\frac{3}{9!}(x-1)(x-2)(x-4)(x-5)(x-6)(x-7)(x-8)(x-9) \\ & & + & a_4\times(-1)^{4-1}\times\frac{4}{9!}(x-1)(x-2)(x-3)(x-5)(x-6)(x-7)(x-8)(x-9) \\ & & + & a_5\times(-1)^{5-1}\times\frac{5}{9!}(x-1)(x-2)(x-3)(x-4)(x-6)(x-7)(x-8)(x-9) \\ & & + & a_6\times(-1)^{6-1}\times\frac{6}{9!}(x-1)(x-2)(x-3)(x-4)(x-5)(x-7)(x-8)(x-9) \\ & & + & a_7\times(-1)^{7-1}\times\frac{7}{9!}(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-8)(x-9) \\ & & + & a_8\times(-1)^{8-1}\times\frac{8}{9!}(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-9) \\ & & + & a_9\times(-1)^{9-1}\times\frac{9}{9!}(x-1)(x-2)(x-3)(x-4)(x-5)(x-6)(x-7)(x-8) \\ \end{array} $$

Where $ a_1 = 2 $, $ a_2 = 4 $, $ a_3 = 6 $, $ a_4 = 8 $, $ a_5 = 10 $, $ a_6 = 12 $, $ a_7 = 14 $, $ a_8 = 16 $ and $ a_9 = -23$.

This may look very long if you are working analytically. But if you are implementing numerical methods in computer, this can be automated and greatly simplified by a simple software algorithm as a general solution to generate arbitrary discrete sequences.