# How to find $P(n+1)$, given $P(x)$ for $x = 0,1,\ldots,n$?

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?

-
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

$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 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
Hamming, in his book, gives a good discussion on the use of differencing for evaluating a polynomial at equispaced points. –  Guess who it is. 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.

-

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.

-