\documentstyle[12pt]{article}
\begin{document}
\begin{center}
Math 192r, Problem Set \#1: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
\begin{enumerate}
\item {\it Write and run a program to compute
$f(n) = \sum_{k=0}^n (-1)^k {n \choose k}^2$.}

Here's one that'll do the job:

\begin{verbatim}
        f := proc(n)
        local k; 
        RETURN(sum((-1)^k*binomial(n,k)^2,k=0..n));
        end;
\end{verbatim}

Notice that the variable {\tt{k}} is declared to be {\tt{local}};
that means that if you had a variable named {\tt{k}} sitting around
in your Maple session before you ran the program {\tt{f}},
the value of the variable won't be affected.

Running the above program for $n=1$ through $n=10$ gives the values
$0$, $-2$, $0$, $6$, $0$, $-20$, $0$, $70$, $0$, $-252$.

Note by the way that you can run into problems with the way Maple
tries to be ``helpful'' by using what it knows.
If you tell Maple
\begin{verbatim}
        a := sum((-1)^k*binomial(n,k)^2,k=0..n);
\end{verbatim}
it will eagerly simplify this to an expression involving the gamma function.
If you then ask it to evaluate this expression for a particular value of $n$,
say by typing ${\tt{subs(n=2,a);}}$,
you'll still get an expression involving the gamma function.
At this point you could gruffly tell it
\begin{verbatim}
        simplify(%);
\end{verbatim}
(or
\begin{verbatim}
        simplify(");
\end{verbatim}
with very old versions of Maple),
meaning ``simplify the expression you just gave me'',
and it will indeed give you the answer $-2$.
But suppose you now type
\begin{verbatim}
        simplify(subs(n=3,a));
\end{verbatim}
Then Maple balks at the fact that the denominator
of $a$ (or rather, the analytic expression for {\tt{a}}
that Maple has introduced)
blows up,
and scrupulously refuses to replace the fraction by 0
even though the numerator is finite and the denominator is infinite.
Ditto for
${\tt{eval(subs(n=3,a));}}$.

All computer algebra systems have features like this;
when you encounter one, please let me know about it!
%
\item 
{\it Devise a conjecture about the value of $f(n)$.}

When $n$ is odd, $f(n)$ vanishes, 
while when $n$ is even (say $n=2m$), $f(2m) = (-1)^m {2m \choose m}$.
%
\item 
{\it Prove your conjecture using the algebraic interpretation of $n \choose k$ 
as the coefficient of $x^k$ in $(1+x)^n$.}

${n \choose k}$ is the coefficient of $x^k$ in $(1+x)^n$,
and $(-1)^k {n \choose k}$ is the coefficient of $x^k$ in $(1-x)^n$.
Hence, as in the example explained in class, 
$f(n)$ is equal to the coefficient of $x^n$ in $(1+x)^n (1-x)^n$.
We can rewrite this polynomial as $(1-x^2)^n$.  Note that all the
exponents in the expansion of this polynomial are even.
Hence, if $n$ is odd, $f(n)=0$ as claimed.
On the other hand, when $n$ is even (say $n=2m$), 
we see that the coefficient of $x^{2m}$ in $(1-x^2)^n$ is equal to
the coefficient of $x^m$ in $(1-x)^n$, which is equal to
$(-1)^m {n \choose m} = (-1)^m {2m \choose m}$, as claimed.
%
\item 
{\it Prove your conjecture using the interpretation of $n \choose k$ 
as the number of combinations of $n$ things taken $k$ at a time.}

As in the example studied in class,
we view this as a problem of signed counting,
where we are choosing a committee of size $n$
from a group consisting of $n$ men and $n$ women,
and where a committee counts as plus or minus
according to whether the number of men is even or odd.

Case I: $n$ is odd.
Every plus committee can be matched up with a minus committee,
and vice versa,
if one simply complements the committee.
That is, if you have a committee with an even (resp.\ odd) number of men,
and you create a new committee consisting of all the people
who weren't on the first committee,
then the new committee will have an odd (resp.\ even) number of men.
Hence the alternating sum is 0.

Case II: $n$ is even, with $n=2m$.
Let's assume that the $n$ men and $n$ women
are married in pairs, and that the couples are numbered 1 through $n$.
Call a committee {\it boring} if it consists entirely of couples, and {\it interesting} otherwise.
I claim that there is a way to pair up each interesting committee
with another interesting committee of opposite sign.  
Namely, find the lowest-numbered person on the committee 
whose spouse isn't on the committee, 
and replace that person by his/her mate.  
You can check (and this fact is important!)\ that
if this operation is performed a second time,
you get back the committee you started with.
Hence the operation gives rise to a way of pairing up 
all the possible interesting committees.
Since this pairing pairs up plus-committees with minus-committees, 
all the interesting committees end up cancelling one another,
and the signed enumeration of all the committees gives the same answer 
as the signed enumeration of just the boring committees.  
But each boring committee, consisting of $m$ men and their wives, 
has sign $(-1)^m$, and the number of boring committees is ${n \choose m}$ 
(since there are $n$ couples from which one must choose $m$ couples).  
Hence the alternating sum is $(-1)^m {n \choose m}$, as claimed. 
(Note that this approach applies to Case I as well:
When $n$ is odd, there are no boring committees.)

Observe that the manifest algebraic analogy
\begin{center} 
${n \choose k}$ \ \ is to \ \ $(-1)^k {n \choose k}$\ \  as
\ \ ${n \choose k}^2$ \ \ is to \ \ $(-1)^k {n \choose k}^2$
\end{center}
is reflected at the combinatorial level
by the way in which we introduce extra structure
(thereby breaking some of the symmetry of the original problem).
When analyzing $\sum (-1)^k {n \choose k}$,
we introduced a {\it special element} of the set.
When analyzing $\sum {n \choose k}^2$,
we introduced a partition of the set into {\it two equal subsets}.
When analyzing $\sum (-1)^k {n \choose k}^2$,
we do not superimpose these extra structures in the most obvious way
(i.e., by dividing the set of people into men and women
and choosing a special person,
or perhaps choosing a special man and a special woman),
but we do in a sense superimpose the two sorts of structure:
we introduce a partition of the set into {\it two equal subsets},
and for {\bf each} element of one subset we choose a {\it special element}
of the other set, in such a way that the two subsets get paired up.
Can anyone come up with a more rigorous way of thinking about this?
% Ask domino!

\end{enumerate}

\item
{\it Define a sequence of functions $f_0(x), f_1(x), f_2(x), ...$ 
where $f_0(x) = x$, $f_1(x) = x$, 
and for all $n>1$, $f_n(x) = ([f_{n-1}(x)]^2+1)/f_{n-2}(x)$.
Thus, $f_2(x) = x + x^{-1}$, $f_3(x) = x + 3x^{-1} + x^{-3}$, etc.}

A good program for this in Maple is
\begin{verbatim}
        f := proc(n) 
        if (n < 2) then x; 
        else expand(simplify((f(n-1)^2+1)/f(n-2))); 
        fi; end;
\end{verbatim}
Note that this is an example of {\it recursive programming}.
Also note that the {\tt{RETURN}} statements have been eliminated.
The value that is returned by a Maple program
is the last value that was computed inside the program,
whether or not it was inside a {\tt{RETURN}} statement.
Note the use of semi-colons;
unfortunately, Maple can be fussy about this.
Also note that, just as each {\tt{proc}} must be matched by an {\tt{end}},
each {\tt{if}} must be matched by {\tt{fi}}
(mnemonic: ``fi'' is ``if'' spelled backwards).

You may be wondering why both {\tt{expand}} and {\tt{simplify}}
are present, and in that particular order.
If you are new to Maple, try to modify this program in various ways
to see whether it still works, and if it does work, what it does.
For instance, what happens if you replace ``{\tt{expand(simplify(...))}}''
by ``{\tt{simplify(expand(...))}}'' or by ``{\tt{simplify(...)}}'' 
or by ``{\tt{expand(...)}}'' or by just ``{\tt{...}}''?
\begin{enumerate}
\item
{\it Formulate a conjecture about the values of $f_n(1)$.}

Typing {\tt{subs(x=1,f(1));}}, {\tt{subs(x=1,f(2));}}, etc.,
we get the values $1, 1, 2, 5, 13, 34, \dots,$
so we conjecture that the sequence of values of $f_n(1)$
consists of every other term of the Fibonacci sequence.
\item
{\it Formulate a conjecture about the values of $f_n(-1)$.}

Typing {\tt{subs(x=-1,f(1));}}, etc.,
we get the values $-1, -1, -2, -5,$ $-13, -34, \dots,$
so we conjecture that the sequence of values of $f_n(1)$
consists of the negative of every other term of the Fibonacci sequence.
In fact, we can prove by induction that each polynomial $f_n(x)$
is an odd function of $x$,
so this conjecture is a trivial consequence of the previous conjecture.

\item
{\it Formulate a conjecture about the values of $f_n(i)$,
where $i = \sqrt{-1}$.}

This time we use {\tt{subs(x=I,f(1));}}, etc.
(Did you figure out that Maple has complex numbers, too?
If you didn't, it's good to know that Maple has a {\tt{help}} facility.
In this case, the command 
\begin{verbatim}
        help(imaginary)
\end{verbatim}
(no semicolons needed for {\tt{help}} commands)
would have told you that the square root of minus one is {\tt{I}}.
Another way to ask the question is just to type 
\begin{verbatim}
        ?imaginary
\end{verbatim}
(again, no semicolon needed).  

Note that if you had used the {\tt{expand(...)}} version of the program
(with no {\tt{simplify(...)}}), you'd find that $f_4(I)$ is undefined,
because of a vanishing denominator in a sub-expression.

To list the values of $f_n(i)$
as $i$ goes from 0 to 10 (say),
here's a handy shortcut:
\begin{verbatim}
        for n from 0 to 10 do subs(x=I,f(n)); od;
\end{verbatim}
({\tt{od}} pairs with {\tt{do}}
just as 
{\tt{fi}} pairs with {\tt{if}}.)
Running this program one gets the sequence of values
$i,i,0,-i,-i,0,i,i,0$,$-i,-i$
displayed vertically down the screen.
One may conjecture that this pattern continues, with period 6.

If you prefer horizontal display, use the {\tt{seq}} operator:
the command
\begin{verbatim}
        [seq(subs(x=I,f(n)),n=0..10)];
\end{verbatim}
gives the sequence of values
in the form of a list.
The opening and closing brackets tell Maple that it is building a list;
we'll learn much more about working with lists later in the term.

\item
{\it Formulate a conjecture about the coefficients
of the polynomials $f_n(x)$.}

{\it Are} they polynomials?  Strictly speaking, they're Laurent polynomials;
that is, they're polynomials in the two variables $x$ and $1/x$.
We write the ring of Laurent polynomials in $x$
(with real coefficients, say)
as ${\bf R}[x,1/x]$.
Compare this with the ring of formal Laurent series in $x$,
which is written as ${\bf R}[1/x][[x]]$ or ${\bf R}[[x]][1/x]$;
here the double brackets around $x$ indicate that
we can form infinite sums in which $x$ gets raised to
arbitrarily large powers.

It's not obvious that the functions in this recurrence
should all be Laurent polynomials!
But this does seem to be the case,
so that should be explicitly included
as part of the conjecture.

We recognize the coefficients as entries from Pascal's triangle,
read off at a slant.
We conjecture that $f_n(x)$ is a Laurent polynomial in $x$
in which the exponents of $x$ are the odd numbers
ranging between $-(2n-3)$ and $1$.
More specifically, we conjecture that for $k$ between 1 and $n$,
the coefficient of $x^{3-2k}$ in $f_n(x)$
is the binomial coefficient $n-2+k \choose 2k-2$.
Later in the course we'll see how to prove this,
both algebraically and combinatorially.

By the way, in order to make the program compact
I defined $f_n(x)$ as $x$ for all $n$ less than 2,
not just $n=1$ and $n=0$;
but is this really the right choice?
What happens when we write the recurrence in the form
$f_{n-2}(x) = ([f_{n-1}(x)]^2+1)/f_n(x)$
and run it backward, using $n=1$, $n=0$, $n=-1$, etc.?
\end{enumerate}
\end{enumerate}

\noindent
Incidentally, to end a Maple session,
all you need to do is type {\tt{quit}}
(no semicolon needed).

\noindent
I should say here (and should have said sooner)
that I am by no means an expert at Maple;
if any of the above comments about programming
seem confusing or incorrect,
please let me know, so that I can correct them!

\end{document}

