\documentclass[12pt]{article}
\begin{document}
\begin{center}
Math 491, Problem Set \#17: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it Let
$p(n)$ be the number of unconstrained partitions of $n$ if $n \geq 0$,
and 0 othewise, so that
$$p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - - + + \dots$$
for all $n > 0$.
Use the recurrence for $p(n)$
to compute the last digit of $p(n)$
for every $n$ between 1 and 1000.
Make a conjecture about the relationship
between the last digit of $n$
and the last digit of $p(n)$;
specifically, make a conjecture about
which pairs $(n \ \mbox{mod} \ 10, \ p(n) \ \mbox{mod} \ 10)$
occur and which don't. }
Here's a Maple program that does this:
\begin{verbatim}
F := proc(n) option remember; local total, k;
if n=0 then 1; elif n<0 then 0; else total := 0;
k := 1; while k*(3*k+1)/2 <= n do
total := total - (-1)^k*F(n-k*(3*k+1)/2): k := k+1: od:
k := -1; while k*(3*k+1)/2 <= n do
total := total - (-1)^k*F(n-k*(3*k+1)/2): k := k-1: od:
total mod 10; fi: end;
\end{verbatim}
We then create a matrix to keep track of
how often it happens that $n$ ends with the digit $i$
while $p(n)$ ends with the digit $j$
(for $i,j$ between 0 and 9),
and print out its entries:
\begin{verbatim}
for i from 0 to 9 do for j from 0 to 9 do a[i,j]:=0: od: od:
for n from 1 to 1000 do k: = F(n);
a[n mod 10, k mod 10] := a[n mod 10, k mod 10] + 1; od:
for i from 0 to 9 do seq(a[i,j],j=0..9) od;
\end{verbatim}
This results in the output
\begin{verbatim}
14, 7, 13, 12, 3, 5, 12, 15, 9, 10
9, 11, 14, 9, 8, 9, 10, 13, 7, 10
3, 14, 12, 14, 10, 8, 8, 12, 6, 13
8, 9, 12, 9, 8, 17, 5, 13, 9, 10
49, 0, 0, 0, 0, 51, 0, 0, 0, 0
5, 12, 10, 4, 15, 7, 13, 13, 8, 13
8, 14, 11, 15, 7, 9, 8, 6, 5, 17
9, 10, 6, 9, 16, 10, 9, 9, 12, 10
10, 9, 16, 8, 11, 11, 11, 13, 5, 6
48, 0, 0, 0, 0, 52, 0, 0, 0, 0
\end{verbatim}
from which we conjecture that when $n$ ends in 4 or 9,
$p(n)$ ends in 0 or 5. That is, if $n$ is 1 less than a multiple of 5,
$p(n)$ is a multiple of 5.
This fact was first noticed and proved by Ramanujan.
Coincidentally, Prof. Ono spoke about this very result
in his Math Club talk yesterday (December 1)!
\item
{\it Let $f(0)=1$
and recursively define
$f(n)=f(n-1)+f(n-3)-f(n-6)-f(n-10)+f(n-15)+f(n-21)--++...$
for all $n>0$,
where terms of the form $f(n-k)$ are to be ignored
once $k > n$.}
\begin{itemize}
\item[(a)]
{Since the formal power series $F(q) = \sum_{n \geq 0} f(n) q^n =
1 + q + q^2 + 2q^3 + 3q^4 + 4q^5 + 5q^6 + 7q^7 + \dots$
has constant term 1,
we saw in class that it admits
a (unique) convergent infinite formal product expansion of the form
$$(1-q)^{a_1} (1-q^2)^{a_2} (1-q^3)^{a_3} (1-q^4)^{a_4} \cdots$$
Find $a_1$ through $a_{24}$,
and conjecture a general rule.}
The defining recursion for $f(n)$ tells us that
$F(q) = 1/(1-q-q^3+q^6+q^{10}-q^{15}-q^{21}+\dots)$.
So we may start from this expression (say using exponents up to 25),
take its formal Taylor series,
and repeatedly divide or multiply by a suitable expession of the form
$(1-q^m)^k$ so as to increase the degree of the first non-constant
term in the (continually modified) series.
More specifically, suppose we start with the command
\begin{verbatim}
taylor(1/(1-q-q\^3+q\^6+q\^10-q\^15-q\^21),q,25);
\end{verbatim}
which returns a power series with constant term 1 and
linear term $q$. We can get the coefficient of the
linear term to become 0 if we multiply by $1-q$.
Entering
\begin{verbatim}
taylor(%*(1-q),q,25);
\end{verbatim}
we get a power
series with constant term 1, no linear term, no
quadratic term, and a cubic term $q^3$. We can get
the coefficient of the cubic term to become 0 if we
multiply by $1-q^3$. So we enter
\begin{verbatim}
taylor(%*(1-q^3),q,25);
\end{verbatim}
And so on.
Proceeding in this fashion, we find that
$a_1 = -1$, $a_2 = 0$, $a_3 = -1$, $a_4 = -1$,
$a_5 = -1$, $a_6 = 0$, $a_7 = -1$, $a_8 = -1$,
etc.; that is, for all $n \leq 24$,
$a_n$ is 0 if $n$ is 2 more than a multiple of 4
and is $-1$ otherwise.
\item[(b)]
{\it Assuming that your answer from (a) is correct,
prove that for a particular set $S$ of positive integers
(which you must find!),
$f(n)$ equals the number of partitions of $n$
into parts belonging to $S$.}
Since $a_n$ is always either $-1$ or $0$, this is simple:
$(1-q)^{a_1} (1-q^2)^{a_2} (1-q^3)^{a_3} (1-q^4)^{a_4} \cdots$
is $\prod_{k \in S} (1-q^k)^{-1}$,
so $S$ is the set of all positive integers
that are either odd or divisible by 4.
\item[(c)]
{\it Prove that your conjectures from (a) and (b) are correct,
e.g. by using the Jacobi triple product identity
$$\prod_{n=1}^\infty (1-x^{2n}) (1+x^{2n-1} z^2) (1+x^{2n-1} z^{-2})
= \sum_{m = -\infty}^\infty x^{m^2} z^{2m}$$
(which you do not need to prove).
An equivalent form of the Jacobi triple product identity is
$$\prod_{i=1}^\infty (1+xq^i) (1+x^{-1}q^{i-1}) (1-q^i)
= \sum_{n = -\infty}^\infty q^{n(n+1)/2} x^{n}.$$}
We want to equate the sum
$$\dots + x^9 z^{-6} + x^4 z^{-4} + x^1 z^{-2} + x^0 z^0
+ x^1 z^2 + x^4 z^4 + x^9 z^6 + \dots$$
(the right hand side of the Jacobi triple product identity)
with the sum
$$\dots - q^{15} + q^6 - q + 1 - q^3 + q^{10} - q^{21} + \dots$$
(the $q$-series we are trying to evaluate in product form)
by making a suitable choice for $x$ and $z$;
we achieve this by setting $x=q^2$ and $z=i\sqrt{q}$
(so that $z^2 = -q$).
Then the left hand side of the Jacobi triple product identity
becomes $\prod_{i=1}^{\infty} (1-q^{4n})(1-q^{4n-1})(1-q^{4n-3})$.
So we have shown that
$$1/F(q) = \prod \frac{1}{1-q^m}$$
where the product is taken over all $m$
that are not 2 more than a multiple of 4.
This is equivalent to what was conjectured in part (b).
\end{itemize}
\end{enumerate}
\end{document}