\documentclass[12pt]{article}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#14: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it Use the recurrence for $p(n)$
to compute the last digit of $p(n)$
for every $n$ between 1 and 1000.
Can you make any conjectures about the relationship
between the last digit of $n$
and the last digit of $p(n)$?}

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.)

\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$.
There exists a set $S$ of positive integers such that
$F(n)$ equals the number of partitions of $n$
into parts belonging to $S$.
Find $S$ (conjecturally).}

This property of $S$ is equivalent to
$1-q-q^3+q^6+q^{10}--++\dots = \prod_{k \in S} (1-q^k)$.
We note first that we must have $1 \in S$,
since if not, every factor in the product would have
vanishing coefficient of $q^1$.
Next we have
$\prod_{k \in S \setminus\{1\}} (1-q^k)
= (1-q-q^3+...)/(1-q) = 1+0q+0q^2-q^3...$.
We now note that we must have $2 \not\in S$,
since otherwise we would have
$\prod_{k \in S \setminus\{1\}} (1-q^k)$ of the form $1-q^2...$.
On the other hand, we must have $3 \in S$.
We now continue with
$\prod_{k \in S \setminus\{1,3\}} (1-q^k)
= (1-q-q^3+q^6...)/(1-q)(1-q^3) = 1+0q+0q^2+0q^3-q^4-q^5-q^7...$
to conclude that 4 and 5 (but not 6) belong to $S$.
And so on.
Empirically, we find that $S$ is just the set of numbers
that are not congruent to 2 mod 4.
\end{enumerate}
\end{document}
