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

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

-
Yes it is possible, and the next numbers are 42, 42, 42, 42, 42, 42, ... –  Did Feb 21 '13 at 22:08
You should say "polynomial" rather than "rule" if you truly are looking for a polynomial. Given the jarring change of behavior of the sequence, the best rule that generates the data is $$f(n) = \begin{cases} 2n+2 & x < 8 \\ -23 & x = 8 \end{cases}$$ –  Hurkyl Feb 22 '13 at 18:07

[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.

-
thanks, i used your method to get the answer. when i tried to use larange interpolation, i started getting long expressions . . . –  rbtLong Feb 21 '13 at 21:16
Erm. It was just very cool how you quickly gave the polynomial for that sequence. I wondered if it had some connection to creating generating functions. –  Cris Stringfellow Feb 21 '13 at 21:18
@CrisStringfellow Ah, no, not generating functins just past experience. You can always interpolate between the points inductively, solving for the first $n$ and then adding a polynomial for the $n+1$st element which is zzero at the other points. –  Thomas Andrews Feb 22 '13 at 13:22
@ThomasAndrews that's a really cool technique, I really like that. Would you know where I could a find a kind of listing of really slick techniques like that? –  Cris Stringfellow Feb 22 '13 at 16:07
@CrisStringfellow I'm not sure how to answer that, but this particular solution can be seen as as an application of the "finite differences" technique to fit a polynomial for a sequence. I've updated my answer to give details. this is related the the Newton Series of a sequence: en.wikipedia.org/wiki/Finite_difference#Newton.27s_series –  Thomas Andrews Feb 22 '13 at 16:31

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.

-
thanks, i can see how to apply larange interpolation now. the terms i got became very long to do using the lagrange interpolation . . . –  rbtLong Feb 21 '13 at 21:14

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.

-
i asked the professor for the answer and he gave me a very short answer . . . it was only 1 expression (1 term long) –  rbtLong Feb 23 '13 at 3:02