\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#6: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it There is a unique polynomial of degree $d$ such that $f(k)=2^k$ for $k=0,1,...,d$. What is $f(d+1)$? What is $f(-1)$?}
Suppose $g(k)$ is a polynomial of degree $m \geq 1$,
so that its sequence of $m$th differences is constant.
If we define $G(k)=g(k)+g(k-1)+\dots+g(1)$ for all $k \geq 1$,
then the first differences of $G$ are the ``zeroeth'' differences of $g$,
the second differences of $G$ are the first differences of $g$,
and so on, so that the sequence of $m+1$st difference of $G$ is constant,
implying that $G(k)$ is given by a polynomial of degree $m+1$ in $k$.
This last assertion is true for $g(k-1)+g(k-2)+\dots+g(0)+1$ as well,
since it differs from $G(k)$ by the substitution
of $k-1$ for $k$ and the addition of the constant 1.
In particular, we see that
if $f$ is a polynomial of degree $d-1$
with $f(k) = 2^k$ for $0 \leq k \leq d-1$,
then the sum $F(k) = f(k-1)+f(k-2)+\dots+f(0)+1$
defines a polynomial function of degree $d$,
and it is easy to see that if $f$ satisfies the property
that characterizes $f_{d-1}$,
$F$ satisfies the property that characterizes $f_d$.
Hence we have
$$f_d(k) = f_{d-1}(k-1)+f_{d-1}(k-2)+\dots+f_{d-1}(0)+1$$
for all $k \geq 0$ (not just $0 \leq k \leq d$),
with the proviso that in the case $k=0$,
the only term on the right hand side is the 1.
Putting $k=d+1$,
we have $f_d(d+1) = f_{d-1}(d)+f_{d-1}(d-1)+\dots+f_{d-1}(0)+1
= f_{d-1}(d)+2^{d-1}+\dots+1+1 = f^{d-1}(d)+2^d$.
That is, the sequence $f_0(1),f_1(2),f_2(3),\dots,$ has
the sequence $1,2,4,\dots$ as its sequence of first differences,
from which it follows (say by induction) that $f_{d-1}(d)=2^d-1$.
On the other hand, for each fixed $d$ the relation
$f_d(k)-f_d(k-1) = f_{d-1}(k-1)$ holds for all $k$,
since it holds for all positive $k$
and since both sides of the equation are polynomials.
Hence we have
$f_d(0)-f_d(-1) = f_{d-1}(-1)$.
Rewriting this as
$f_d(-1)=f_d(0)-f_{d-1}(-1)$
and using the fact that $f_d(0)=1$,
we have
$f_d(-1)=1-f_{d-1}(-1)$,
from which it follows (say by induction)
that $f_d(-1) = 1$ when $d$ is even and $0$ when $d$ is odd.
(Or, if you prefer formulas,
$f_d = (1 + (-1)^n)/2$.
Note that you don't need to have an explicit formula for $f_d(k)$
in order to solve this problem!
\end{enumerate}
\medskip
\noindent
\end{document}