\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\input{preamble.tex}

\begin{document}

\homework{2: Generating Functions}{Due Friday, Week 3}

Solve the following three problems!  
\begin{enumerate}
\item Consider the Perrin sequence, which we can define recursively as follows: set $r_0 = 3, r_1 = 0, r_2 = 2$, and for all $n \geq 3$ define $r_n = r_{n-2} + r_{n-3}.$

\begin{center}
\includegraphics[width=5in]{FoxTrot20051011.jpg}\\
\footnotesize The fourth panel of the FoxTrot cartoon above contains the first six values of the Perrin sequence.
\end{center}

Let $R(x)$ denote the generating function $\displaystyle R(x) = \sum_{n=0}^\infty r_n x^n$ for the Perrin sequence.
\begin{enumerate}
\item Prove that $ R(x) = \frac{3-x^2}{1-x^2-x^3}$.
\item Use this generating function to create a closed form for $r_n$.
\item Prove that $r_{n} = r_{n-1} + r_{n-5}$, for all $n \geq 5$.
\item Prove the following ``spiral'' relation for the Perrin numbers: 
\begin{center}
\includegraphics[width=4in]{perrin_spiral.pdf}
\end{center}
That is: start with the spiral drawn above, and rotating clockwise extend it by repeatedly drawing equilateral triangles with appropriate side lengths.  Prove that the side lengths of these equilateral triangles are precisely the Perrin numbers starting from $p_4$.
\end{enumerate}
\item Here's a fun/strange fact: if $p$ is a prime number, then $p$ divides $r_p$, the $p$-th Perrin number.  We prove this in this problem, using the techniques of generating functions, as follows:
\begin{enumerate}
\item Define $Q(x) = R(x) - 3;$ that is, $Q(x)$ is the same power series as $\displaystyle R(x) = \sum_{n=0}^\infty r_nx^n$, except we make the constant term zero for calculational convenience.

Show that 
\begin{align*}
Q(x) = (-x) \cdot \frac{d}{dx} \left( \ln (1-x^2 - x^3)\right).
\end{align*}
\item Show that
\begin{align*}
\frac{d^p}{dx^p} \left( Q(x)\right) \Bigg|_{x=0} = (-p) \cdot (p!) \cdot( \textrm{ the coefficient of }x^p\textrm{ in the Taylor series for }\ln(1-x^2 - x^3) ).
\end{align*}
\item Show that on the other hand, if $Q(x)$ is any power series $\sum_{n=0}^\infty r_nx^n$, then
\begin{align*}
\frac{d^p}{dx^p} \left( Q(x)\right) \Bigg|_{x=0} = p! \cdot r_p.
\end{align*}
\item Using the above, prove that $p$ is a factor of $r_p$ whenever $p$ is prime.
\end{enumerate}

\item Let $b_n$ denote the number of ways to create a $2 \times 2 \times n$ pillar using $2 \times 1 \times 1$ bricks.  
\begin{enumerate}
\item Prove that the recurrence relation $b_n = 3b_{n-1} + 3b_{n-2} - b_{n-3}$ holds for all $n \geq 4$.
\item Find a closed form for the generating function $\displaystyle B(x) = \sum_{n=0}^\infty b_n x^n$.
\item Use this to find a closed form for the $b_n$'s.
\item What is $b_{25}$?
\end{enumerate}
\end{enumerate}


\section*{Extra Credit}
Solve the following problem if you're curious!
\begin{enumerate}
\item 
Let $c_n$ denote the number of maximal independent\footnote{For this problem, a subset is called \textbf{independent} if it does not contain any two consecutive numbers, where we regard $1$ and $n$ as consecutive; it is called maximal if there is no set that contains this set as a proper subset and is also independent.} subsets of $\{1,2,\ldots n\}$.  
\begin{enumerate}
\item Prove that $c_n = r_n$ for any $n \geq 2$, where $r_n$ is the Perrin sequence.
\item Consider the map $f: \{1, \ldots n\} \to \{1, \ldots n\}$ that cyclically shifts our set by $+1$; that is, $f(x) = x+1$ for $x \neq n$ and $f(n) = 1$.  For any subset $A$ of $\{1, \ldots n\}$, let $f(A) = \{f(a) ~|~ a \in A\}$.  Show that there is no independent set $A$ such that $f(A) = A$.  Use this fact to offer a non-generating-function proof that $p$ divides $r_p$ for any prime $p$.
\end{enumerate}
\end{enumerate}

\end{document}