\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#7: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it One basis for the space of polynomials of degree less than $d$
is the monomial basis $1,t,t^2,...,t^{d-1}$.
Another is the shifted monomial basis $1,(t+1),(t+1)^2,...,(t+1)^{d-1}$.
Call these bases $u_1,...,u_d$ and $v_1,...,v_d$ respectively.}
\begin{itemize}
\item[(a)]
{\it Derive a formula for the entries of
the change-of-basis matrix $M$ expressing the $u_i$'s
as linear combinations of the $v_j$'s.}
We seek a $d$-by-$d$ matrix $M$ that,
when multiplied on the right by the column vector $e_i$
(with a 1 in the $i$th position and a 0 everywhere else),
gives a column vector $(c_1,c_2,\dots,c_d)^T$
such that $u_i = c_1 v_1 + c_2 v_2 + \dots + c_d v_d$.
Now $u_i = t^{i-1} = ((t+1)-1)^{i-1}
= \sum_{j=0}^{i-1} {i-1 \choose j} (t+1)^j (-1)^{i-1-j}
= \sum_{j=0}^{i-1} {i-1 \choose j} v_{j+1} (-1)^{i-1-j}
= \sum_{j=1}^{i} {i-1 \choose j-1} v_j (-1)^{i-j}$,
so $c_j = (-1)^{i-j} {i-1 \choose j-1}$
(which gets interpreted as 0 for $j>i$).
Hence
$$M_{j,i} = \left\{ \begin{array}{cl}
(-1)^{i-j} {i-1 \choose j-1} & \mbox{for $1 \leq j \leq i \leq n$}, \\
0 & \mbox{otherwise}. \end{array} \right.$$
(Note: I didn't specify whether the vectors were to be treated
as row-vectors or column-vectors, or equivalently,
whether the change-of-basis matrix was supposed to be
applied on the right or on the left. If you adopted the
row-vector approach, you would find that the answers you
got for parts (a) and (b) are reversed, relative to mine.)
\item[(b)]
{\it Derive a formula for the entries of
the change-of-basis matrix $N$ expressing the $v_j$'s
as linear combinations of the $u_i$'s.}
This one is even easier:
$v_j = (t+1)^{j-1}
= \sum_{i=0}^{j-1} {j-1 \choose i} t^i
= \sum_{i=1}^{j} {j-1 \choose i-1} u_i$
so
$$N_{i,j} = \left\{ \begin{array}{cl}
{j-1 \choose i-1} & \mbox{for $1 \leq i \leq j \leq n$}, \\
0 & \mbox{otherwise}. \end{array} \right.$$
\item[(c)]
{\it From the description of $M$ and $N$ as basis-change matrices,
we know that $MN = NM = I$.
Forgetting for the moment what $M$ and $N$ mean,
rewrite the assertions $MN = NM = I$
as binomial coefficient identities,
and prove them either algebraically or bijectively.}
The assertion $MN=I$ can be rewritten as
$\sum_j M_{i,j} N_{j,k} = \delta_{i,k}$,
where $\delta_{i,j}$ is 1 if $i=j$ and 0 otherwise.
That is,
$\sum (-1)^{j-i} {j-1 \choose i-1} {k-1 \choose j-1} = \delta(i,k)$
where the sum is over all $j$ such that
$i \leq j \leq k$. For convenience, we shift indices
and write this as
$$\sum (-1)^{j-i} {j \choose i} {k \choose j} = \delta(i,k)$$
where the sum is still over all $j$ such that
$i \leq j \leq k$.
Algebraic proof: The sum in question is the coefficient of $x^{k-i}$
in the product of
${i \choose i} - {i+1 \choose i} x + {i+2 \choose i} x^2 - \dots
+(-1)^{k-i} {k \choose i} x^{k-i} + \dots$
and
${k \choose k} + {k \choose k-1} x + {k \choose k-2} x^2 + \dots
+{k \choose i} x^{k-i} + \dots + {k \choose 0} x^k$.
The first factor can be recognized as $(1+x)^{-(i+1)}$
(by the binomial theorem) and the latter can be recognized as
$(1+x)^k$. So the product is $(1+x)^{k-i-1}$.
The coefficient of $x^{k-i}$ in the formal power series expansion
of $(1+x)^{k-i-1}$ is 0 as long as $k-i-1$ is non-negative,
since in that case $(1+x)^{k-i-1}$ is just a polynomial
of degree less than $k-i$.
However, when $i=k$, $(1+x)^{k-i-1}$ becomes the formal power series
$(1+x)^{-1} = 1 - x + x^2 - x^3 + \dots$,
in which the coefficient of $x^{k-i}$ is just the constant term 1.
Combinatorial proof: Given a set $C$ of size $k$,
$\sum (-1)^{j-i} {j \choose i} {k \choose j}$
counts the number of ways to choose a subset $B \subset C$ of size $j$
and a subset $A \subset B$ of size $i$,
where a choice of $A,B,C$ counts as positive or negative
according to whether the number of elements of $B$ that are not in $C$
is even or odd.
If we hold the subset $A$ fixed and do a signed enumeration
of the sets $B$ satisfying $A \subset B \subset C$,
we find that the signed count is 1 if $A=C$
and 0 otherwise.
(Reason: This is just like signed enumeration of
the subsets of $C \setminus A$,
where a set counts as positive or negative
according to whether it has an even or odd number of elements.)
If $i=k$, there is exactly one set $A$, namely $C$ itself,
whose aggregate contribution is non-zero,
and in this case the aggregate contribution is 1;
whereas if $i