Solving for $f(n+1)$ when $f(k)$ is known for $k=0,1,...,n$ I posted earlier about polynomials but this is different type of problem I think.  I seem to have an answer but I mistrust it....
A polynomial $f(x)$ where deg[$f(x)$]$\le{n}$ satisfies $f(k)=2^k$ for $k=0,1,...,n$.  Find $f(n+1)$.
So $f(k)=2^k \Rightarrow 2^{-k}f(k)-1=0.$  Thus, there exists a constant c such that 
$$2^{-k}f(k)-1=cx(x-1)(x-2)...(x-n)$$
Now, let $x=n+1$.  Then
$$2^{-(n+1)}f(n+1)-1=c(n+1)(n+1-1)(n+1-2)...(n+1-n)=c(n+1)!$$
Therefore, $f(n+1)=2^{n+1}[c(n+1)!+1]$.  Plugging in known values of k we obtain $c=0$ which just shows that $f(n+1)=2^{n+1}$.
Is this right?  It seems right, but I've seen another problem of the sort and it plays out differently.
 A: You are right to mistrust your answer: it's easy to check that it's incorrect in the case $n=1$ (and, for that matter, $n=0$). The mistake you made is in concluding that $2^{-k}f(k) - 1$ must have a certain form; that expression is not a polynomial, so you can't use results about polynomials to categorize it.
In fact, you're not off by that much: the answer is that $f(n+1) = 2^{n+1}-1$. (This gives the right value for $n=0$ and $n=1$, and you can check without too much difficulty that it's also right for $n=2$; that's probably enough data to suggest the pattern.) To me, the nicest way to solve this problem is to prove it by induction on $n$.
For clarity, let $f_n$ denote the polynomial described in the problem for a particular $n$. Then consider
$$f_n(x+1) - f_n(x).$$
Given what we know about $f_n$, we can show that this new expression is a polynomial of degree at most $n-1$, and its values at $x=0,1,\dots,n-1$ are $1,2,\dots,2^{n-1}$. In other words, $f_n(x+1) - f_n(x)$ must equal $f_{n-1}(x)$! And now the induction hypothesis should give you what you want almost immediately.
