2
$\begingroup$

Given $P$, a polynomial of degree $n$, such that $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?

  • 0
    He said $P(x)$ is a polynomial of degree $n$ with the specific values for $x=0,...,n$.2012-07-17

3 Answers 3

8

$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) 
  • 1
    Hamming, in [his book](http://books.google.com/books?hl=en&id=Y3YSCmWBVwoC&pg=PA155), gives a good discussion on the use of differencing for evaluating a polynomial at equispaced points.2012-07-18
4

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.

1

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.