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.

Given $P$, a polynomial of degree $n$, such that its values at $n+1$ points are $P(x) = r^x$ for $x = 0,1, \ldots, n$ and some real number $r$, I need to calculate $P(n+1)$?

Can this be done without Lagrange interpolation?

share|improve this question
    
If $P(x) = r^x,$ then $P(n+1) = r^{n+1} = r^n r = P(n)P(1).$ Am I mis-reading the question? –  user2468 Jul 17 '12 at 21:36
    
@J.D. It seems that holds only for $x=1..n$, so we can't be sure about $n+1$. –  Pedro Tamaroff Jul 17 '12 at 21:41
    
He said $P(x)$ is a polynomial of degree $n$ with the specific values for $x=0,...,n$. –  Thomas Andrews Jul 17 '12 at 21:47

3 Answers 3

$P(n+1) = r^{n+1}-(r-1)^{n+1}$.

Construct the successive differences between terms, thus:

1         r            r^2               r^3  ...               r^n  
    r-1         r(r-1)        r^2(r-1)  ...         r^(n-1)*(r-1)
        (r-1)^2      r(r-1)^2      ...
                 ...
                        (r-1)^n

These are all known. Consider the top line to be the $0$th line, so that the last one is the $n$th line. Now interpolate the polynomial: the next term on the last line will also be $(r-1)^n$. You can then work your way back up to the top, and it is straightforward to show that the last term on the $k$th line will be $(r-1)^k\big((r-1)^{n+1-k}-r^{n+1-k}\big)$.

Example with $r=10$, $n=3$ (the interpolation is on the right):

   1   10       100      1000  |                3439 = 9^0*(10^4 - 9^4)
     9      90       900       |           2439      = 9^1*(10^3 - 9^3)
        81      810            |      1539           = 9^2*(10^2 - 9^2)
           729                 |  729                = 9^3*(10^1 - 9^1)
share|improve this answer
1  
+1 nice answer. Don't you mean $P(n+1) = r^{n+1} - (r-1)^{n+1}$? –  Erick Wong Jul 17 '12 at 23:39
    
@ErickWong Yes, thanks for catching that. It's fixed. –  Théophile Jul 18 '12 at 0:14
1  
Hamming, in his book, gives a good discussion on the use of differencing for evaluating a polynomial at equispaced points. –  J. M. Jul 18 '12 at 2:25

By the binomial theorem, $$r^x = \sum_{k=0}^{\infty} \binom{x}{k} (r-1)^k$$ for any $x$. Now, if $x$ is a integer from $0$ to $n$, then $\binom{x}{k}=0$ for $k>n$. So $$r^x = \sum_{k=0}^n \binom{x}{k} (r-1)^k \quad \mbox{for} \ x \in \{ 0,1,2,\ldots, n \}.$$

Notice that the right hand side is a degree $n$ polynomial in $x$. So $$P(x) = \sum_{k=0}^n \binom{x}{k} (r-1)^k \ \textrm{and}$$ $$P(n+1) = \sum_{k=0}^n \binom{n+1}{k} (r-1)^k.$$ Using the binomial theorem one more time $$P(n+1) = r^{n+1}-(r-1)^{n+1}$$ as in Theophile's answer.

share|improve this answer

Via Lagrange polynomials you can fit a finite number of points exactly, and then plug $n+1$ into the polynomial you get.

I'm not sure that fully answers the question, even though it gives you a way to find the right number in every particular case. That is because there's the further question of whether the values of $P(n+1)$ follow some general pattern resulting from the particular form of the exponential function $x\mapsto r^x$ and the fact that it's $n+1$, the next number in that arithmetic sequence, rather than some other number.

share|improve this answer

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.