\documentclass{article}

\usepackage{amsmath}
% \usepackage{hyperref}

\usepackage{amssymb}
\usepackage{bm}
%usepackage{amsfonts}%This is to have nice letters
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{psfrag}
\usepackage{multicol}
%usepackage{showkeys}
\usepackage{color}
\usepackage{url}
% \usepackage{mathabx}

\usepackage{algpseudocode}

\usepackage{mathtools}

\usepackage{xy}
\input xy
\xyoption{all}

\setlength{\hoffset}{-0.5in}
\addtolength{\textwidth}{1.0in}
\setlength{\voffset}{-0.5in}
\addtolength{\textheight}{1.0in}

\newcommand{\excise}[1]{}%{$\star$\textsc{#1}$\star$}
\newcommand{\comment}[1]{{$\star$\sf\textbf{#1}$\star$}}

%\numberwithin{section}{part}
%\renewcommand\thepart{\Roman{part}}
% Theorem environments with italic font
\newtheorem*{thm}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{claim}{Claim}
\newtheorem*{cor}{Corollary}
\newtheorem*{prop}{Proposition}
\newtheorem*{conj}{Conjecture}
\newtheorem*{question}{Question}
\newtheorem*{prob}{Problem}

\theoremstyle{definition}
\newtheorem*{alg}{Algorithm}
\newtheorem*{example}{Example}
\newtheorem*{remark}{Remark}
\newtheorem*{defn}{Definition}
\newtheorem*{conv}{Convention}
\newtheorem*{obs}{Observation}

\numberwithin{equation}{section}

%For numbered lists with arabic 1. 2. 3. numbering
\renewcommand\labelenumi{\theenumi.}

%For separated lists with consecutive numbering
\newcounter{separated}

\newcommand{\ring}[1]{\ensuremath{\mathbb{#1}}}

%single characters, used in math mode
\renewcommand\>{\rangle}
\newcommand\<{\langle}
\newcommand\0{\mathbf{0}}
\newcommand\CC{\ring{C}}
\newcommand\KK{{\mathcal K}}
\newcommand\MM{{\mathcal M}}
\newcommand\NN{\ring{N}}
\newcommand\OO{{\mathcal O}}
\newcommand\QQ{\ring{Q}}
\newcommand\RR{\ring{R}}
\newcommand\TT{{\mathcal T}}
\newcommand\ZZ{\ring{Z}}
\newcommand\dd{{\mathbf d}}
\newcommand\kk{\Bbbk}
\newcommand\mm{{\mathfrak m}}
\newcommand\nn{{\mathfrak n}}
\newcommand\pp{{\mathfrak p}}
% \newcommand\qq{{\mathfrak q}}
\newcommand\ww{{\mathbf w}}
\newcommand\xx{{\mathbf x}}
\newcommand\cA{{\mathcal A}}
\newcommand\cB{{\mathcal B}}
\newcommand\cC{{\mathcal C}}
\newcommand\cG{{\mathcal G}}
\newcommand\cP{{\mathcal P}}
\newcommand\cW{{\mathcal W}}
\newcommand\oA{\hspace{.35ex}\ol{\hspace{-.35ex}A\hspace{-.2ex}}\hspace{.2ex}}
\newcommand\oJ{{\hspace{.45ex}\overline{\hspace{-.45ex}J}}}
\newcommand\oQ{\hspace{.15ex}\ol{\hspace{-.15ex}Q\hspace{-.25ex}}\hspace{.25ex}}
\newcommand\ttt{\mathbf{t}}
\renewcommand\aa{{\mathbf a}}
\newcommand\bb{{\mathbf b}}
\newcommand\ee{{\mathbf e}}

\newcommand\free{{\mathcal F}}
\renewcommand\AA{{\mathcal A}}
\newcommand\qq{{\mathsf q}}

%roman font words for math mode
\newcommand\gp{\mathrm{gp}}
\newcommand\emb{\mathrm{emb}}
\newcommand\tor{\mathrm{tor}}
\renewcommand\th{\mathrm{th}}

%math symbols without arguments
\newcommand\app{\mathord\approx}
\newcommand\can{0}
\newcommand\iso{\cong}
\newcommand\nil{\infty}
\newcommand\ott{\ol\ttt{}}
\newcommand\til{\mathord\sim}
\newcommand\too{\longrightarrow}
\newcommand\Iqp{I_q{}^{\hspace{-.7ex}P}}
\newcommand\Irp{I_{\rho,P}}
\newcommand\Isp{I_{\sigma,P}}
\newcommand\Mwp{M_\ww^P}
\newcommand\rqp{\rho_q^{\hspace{.2ex}P}}
\newcommand\Iaug{I_{\mathrm{aug}}}
\newcommand\Irpp{I_{\rho',P'}}
\newcommand\MipI{M_\infty^P(I)}
\newcommand\MrpI{M_\rho^P(I)}
\newcommand\MspI{M_\sigma^P(I)}
\newcommand\MwpI{M_\ww^P(I)}
\newcommand\Qlqp{Q_{\preceq q}^P}
\newcommand\Qlwp{Q_{\preceq w}^P}
\newcommand\WwpI{W_\ww^P(I)}
\newcommand\appq{\begin{array}{@{}c@{}} \\[-4ex]\scriptstyle\app%
					\\[-1.6ex]q\\[-.3ex]\end{array}}
\newcommand\appw{\begin{array}{@{}c@{}} \\[-4ex]\scriptstyle\app%
					\\[-1.6ex]w\\[-.3ex]\end{array}}
\newcommand\into{\hookrightarrow}
\newcommand\onto{\twoheadrightarrow}
\newcommand\rqpP{\rho_q^{\hspace{.2ex}P'}}
\newcommand\rpqP{\rho_{p+q}^{\hspace{.2ex}P}}
\newcommand\spot{{\hbox{\raisebox{1.7pt}{\large\bf .}}\hspace{-.5pt}}}
\newcommand\void{{\{\}}}
%newcommand\defas{:=}
\newcommand\minus{\smallsetminus}
\newcommand\nothing{\varnothing}
\newcommand\appqscript{{\begin{array}{@{}c@{}}%
			\\[-4.8ex]\scriptscriptstyle\app%
			\\[-1.9ex]\scriptstyle q\\[-1ex]%
			\end{array}}}
\renewcommand\iff{\Leftrightarrow}
\renewcommand\implies{\Rightarrow}

%math symbols taking arguments
\def\ol#1{{\overline {#1}}}
\def\wh#1{{\widehat {#1}}}
\def\wt#1{{\widetilde {#1}}}
\newcommand\set[1]{\{#1\}}
\newcommand\abs[1]{|#1|}

%Math operators
\DeclareMathOperator\Hom{Hom} % Hom
\DeclareMathOperator\image{Im} % Hom
% \DeclareMathOperator\Mod{-Mod} % Q-Mod, R-Mod
\DeclareMathOperator\ann{ann} % Annihilator
\DeclareMathOperator\Ass{Ass} % Associated Primes 
\DeclareMathOperator\sat{sat} % saturation of a lattice
\DeclareMathOperator\soc{soc} % socle of a module
\DeclareMathOperator\Hull{Hull} % Hull - localization
\DeclareMathOperator\Spec{Spec} %
\DeclareMathOperator\coker{coker} % cokernel
\DeclareMathOperator\Aut{Aut} % Aut

\DeclareMathOperator\lcm{lcm} % lcm
\DeclareMathOperator\Ap{Ap} % Apery set
\DeclareMathOperator\supp{supp} % support
\DeclareMathOperator\bul{bul} % bullets
\DeclareMathOperator\mbul{mbul} % maximal bullets

\DeclareMathOperator\Conv{conv} % conv



% Replaces \atop
\newcommand{\aoverb}[2]{{\genfrac{}{}{0pt}{1}{#1}{#2}}}
%0 = displaystyle               in the 4th argument
%1 = textstyle
%2 = scriptstyle
%3 = scriptscriptstyle
\def\twoline#1#2{\aoverb{\scriptstyle {#1}}{\scriptstyle {#2}}}


\begin{document}

\begin{center}
\textbf{Spring 2026, Math 590:\ Week 2 Problem Set} \\
\textbf{Due:\ Wednesday, February 11th, 2026} \\
\textbf{Introduction to Generating Functions}
\end{center}


\begin{center}
\begin{tabular}{r@{\,\,\,}p{4in}}
Name: & 
% INSERT NAME HERE
X
\\
Collaborators: & 
% LIST COLLABORATORS HERE
X, X, X
\end{tabular}
\end{center}


\bigskip
\noindent
\textbf{Homework problems.}
You must submit \emph{all} homework problems in order to receive full credit.  

\begin{enumerate}[(H1)]
\item 
Find a rational expression for $A(z) = \sum_{\ge 0} a_n z^n$ in terms of $z$ for each of the following sequences $a_n$.  Your answer should \textbf{not} contain any ``$\cdots$'' or sigma-sums.  

Hint:\ you can substantially shorten the algebra needed to obtain your answer with clever use of power series we have already encountered.  

\begin{enumerate}[(a)]
\item 
$a_n = n^3 + 7n^2 + 3n - 5$

\begin{proof}[Answer]

\end{proof}


\item 
$a_n = n2^n - n^2 3^n$

\begin{proof}[Answer]

\end{proof}

\end{enumerate}


\item 
Find a formula for $a_n$ for each of the following power series $A(z) = \sum_{n \ge 0} a_n z^n$.  

Note:\ your formula for $a_n$ should be in terms of $n$ and have no sigma-sums in it!  

\begin{enumerate}[(a)]
\item 
$A(z) = \displaystyle\frac{1}{2 + z}$

\begin{proof}[Answer]

\end{proof}


\item 
$A(z) = \displaystyle\frac{5 + 2z + z^2}{1 - z^3}$

\begin{proof}[Answer]

\end{proof}


\item 
$A(z) = \displaystyle\frac{z^2 + 1}{(1 - z)^3}$

Hint:\ start by writing this series as a combination of those from Problem~(D2).  

\begin{proof}[Answer]

\end{proof}


\end{enumerate}

\item 
Let $A(z) = \sum_{n = 0}^\infty a_n z^n = a_0 + a_1z + a_2z^2 + \cdots$.  
Prove that $A(z)$ has a multiplicative inverse if and only if $a_0 \ne 0$.  Hint:\ if $A(z)B(z) = 1$ for some $B(z) = b_0 + b_1z + b_2z^2 + \cdots$, show each $b_n$ is determined by $a_0, a_1, \ldots, a_n$.  

\begin{proof}

\end{proof}


\item 
Define $c(n) = 1$ if there exists a way to write $n$ as a sum of the values $3$ and $5$, and $c(n) = 0$ otherwise.  For instance, $c(13) = 1$ since $13 = 3 + 5 + 5$, and $c(15) = 1$ since $15 = 5 + 5 + 5$ (as well as $15 = 3 + 3 + 3 + 3 + 3$), but $c(7) = 0$ since there is no way to add $3$'s and $5$'s together to obtain $7$.  Prove that
$$\sum_{n = 0}^\infty c(n)z^n = \frac{1 - z^{15}}{(1 - z^3)(1 - z^{5})}.$$
Note:\ $c(0) = 1$ since $0 = 0 \cdot 3 + 0 \cdot 5$.  

\begin{proof}

\end{proof}

\end{enumerate}



\bigskip
\noindent
\textbf{Challenge problems.}
Challenge problems are not required for submission, but bonus points will be awarded for submitting a partial attempt or a complete solution.  

\begin{enumerate}[(C1)]
\item 
Conjecture and prove an analogous result to Problem~(H4) where positive integers $n_1$ and~$n_2$ replace $3$ and $5$.  

\begin{proof}

\end{proof}

\end{enumerate}

\end{document}

