Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

3 Answers

up vote 25 down vote accepted

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

share|improve this answer
    
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
1  
@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
1  
@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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.