\documentclass[12pt]{amsart}
% Call packages that allow you to invoke certain mathematical symbols.
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=0.9in]{geometry}
\usepackage{cases}
% Set the title, author, and date information.
% Formally begin the document and make the title.
\begin{document}
\noindent \textbf{Math 315 - Fall 2017 \\
Homework 6} \\
Due November 8, 2017 \vspace{-4mm}\\
\noindent \small \textit{Let us subjugate a collection of objects taking into account their qualities and differences each from another, then we are lead, in our mathematical perspective, to the study of integers and their connecting operations, that is, we are lead to Number Theory.
\\
If we, however, disregard the qualities of each individual object and only account for the difference between two objects insofar that they are different, then we are lead to investigations which are concerned with the position, the order, the choosing of these objects. This branch of mathematics is called Combinatorics.}\\\vspace{1mm} \hfill---
Eugen Netto
\vspace{-5mm}
\normalsize
\noindent \hrulefill
\vspace{3mm}\\
\noindent \textbf{Turn in:}
\vspace{5mm}
\bigskip
\begin{enumerate}
\item (Exercise 26, Chapter 8) Let $b_0=1$ and for $n\ge 1$ let $b_n$ satsify the following recurrence relation:
\[b_{n+1} = 3 b_{n} +2^n\]
\begin{enumerate}
\item Find the generating function for the numbers $b_n$.
\item Find a closed formula for $b_n$.
\end{enumerate}
\item (Exercise 27, Chapter 8) A certain kind of insect population multiplies so that at the end of each year,
its size is the double of its size a year
before, plus 1000 more insects.
Assuming that originally we released 50 insects, how many of them will we have at the end of the $n$th year?
\bigskip
\item Suppose we are creating fruit baskets containing apples, oranges, bananas, pears, and peaches with the following conditions:
\begin{itemize}
\item Each basket contains an even number of apples.
\item The number of oranges in each basket is a multiple of three.
\item Each basket contains at most 2 bananas, at most 1 pear, and at most 1 peach.
\end{itemize}
Let $c_n$ be the number of such baskets that contain $n$ pieces of fruit.
\begin{enumerate}
\item Find the generating function for $c_n$.
\item Use the generating function to find a formula for $c_n$.
\end{enumerate}
\item A permutation is indecomposable if it cannot be cut
into two parts so that everything before the cut is smaller than everything
after the cut. For example 3142 is indecomposable, but 2143 is not as you
can cut it after the first two elements. Let $f_n$ be the number of indecomposable
permutations of length $n$ and set $f_0 = 0$. Find the ordinary generating
function $F(x) = \sum_{n=0}^\infty f_n x^n$ in terms of the generating function $G(x) = \sum_{n=0}^\infty n! x^n$, the generating function of all permutations.
\item Find a generating function for the number of ways to make change for $n$ cents using only pennies, nickles, dimes and quarters. Use this generating function to find the number of ways to make change for \$1.99.
\end{enumerate}
\end{document}