How to find $P(n+1)$, given $P(x)$ for $x = 0,1,\ldots,n$? 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?
 A: $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)

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