\documentclass[11pt]{amsart}
\usepackage{graphicx}
\usepackage{amssymb}

\textwidth = 6.5 in
\textheight = 8.5 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.5 in
\headsep = 0.2 in
\parskip = 0.2in
\parindent = 0.0in

\newcommand{\pchoose}[2]{\begin{pmatrix}#1\\ #2\end{pmatrix}}
\newcommand{\bchoose}[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}


\title{Homework \#2 - Math 4160}
\author{Assigned: Oct 5, 2019 Due: Oct 23, 2019}
\begin{document}
\maketitle


Write your homework solutions clearly and in \LaTeX.  Provide full
explanations and justify all of your answers.  You may use the computer
to complete calculations, but please describe the calculation you asked
the computer to do (provide the input and output in some form).

\begin{enumerate}
\item Let $A(x) = \sum_{n \geq 0} a_n x^n$ be the generating function for the sequence
$a_0, a_1, a_2, a_3, \ldots$.   Any term in this sequence can be calculated from the generating
function
by $a_r = \frac{1}{r!}\frac{d^r}{dx^r} A(x) |_{x=0}$
so you may use $a_r$ in your formula for any fixed $r$.
%and $B(x) = \sum_{n \geq 0} b_n x^n$ is the generating
%function for the sequence $b_0, b_1, b_2, b_3, \ldots$.
Give a formula in terms of $A(x)$ and $a_r$ (for any fixed $r \geq 0$) %and $B(x)$
for the generating function of the sequence:
\begin{enumerate}
\item the $n^{th}$ Fibonacci number times the $n^{th}$ term in the sequence:
$a_0 F_0, a_1 F_1, a_2 F_2, a_3 F_3, \ldots$ where $F_0=1, F_1=1, F_2=2, F_3=3, \ldots$
is the Fibonacci sequence.  
\item first differences:
$a_1 - a_0, a_2-a_1, a_3-a_2, \ldots$.
\item delete $a_3$ : $a_0, a_1, a_2, a_4, a_5, a_6, a_7, \ldots$
\item sum of adjacent terms:
$a_0 + a_1, a_1 + a_2, a_2 + a_3, a_3 + a_4, \ldots$.
\end{enumerate}
Hint: For part (a) will use the expression that I derived for the Fibbonaci numbers
involving the golden ratio.
\item In class I said how to prove (its in the notes too)
that $B_k(x) = \sum_{m\geq0} \binom{m}{k} x^m = \frac{x^k}{(1-x)^{k+1}}$.
\begin{enumerate}
\item Starting with the formula for $B_k(x)$,
derive an equation for $A_k(x)=\sum_{m\geq0} m \binom{m}{k} x^m$
\item Show that $A_k(x)= k B_k(x)+ (k+1) B_{k+1}(x)$
\item Derive an identity by taking the coefficient of $x^n$ on both sides of the equation.
\item Give a combinatorial argument which proves the same identity.
\end{enumerate}

\item As in the last problem let
$B_k(x) = \sum_{m\geq0} \binom{m}{k} x^m = \frac{x^k}{(1-x)^{k+1}}$.
\begin{enumerate}
\item Give an expression for the generating function
$A(x,z) = \sum_{k \geq 0} \sum_{m \geq 0}
\binom{m}{k} x^m z^k = \sum_{k \geq 0} B_k(x) z^k~.$
\item Show that by setting $z=1$, $A(x,1)= \frac{1}{1-2x} = \sum_{k \geq 0} \sum_{m \geq 0}
\binom{m}{k} x^m$.  Find an identity by taking the coefficient
of $x^n$ on both sides of the equation.
\item Show that $A(3x, \frac{-x}{3}) = \frac{1}{1-3x+x^2} = \sum_{k \geq 0} \sum_{m \geq 0}
\binom{m}{k} (3x)^m (-x/3)^k$.  Since the coefficient of $x^n$ in $\frac{1}{1-3x+x^2}$ is
$F_{2n+1}$,
show how the generating function can be used to
give a formula for $F_{2n+1}$ in terms of binomial coefficients and powers of $3$.
What does your formula say in particular about $F_9$?
\end{enumerate}


\item Let $G(x) = \sum_{n\geq0} F_n^2 x^n = \frac{1-x}{(1+x)(1-3x+x^2)}$.
Write down an algebraic expression
for the generating function of 
$$F_{n+3}^2 + F_n^2$$ 
and another for the generating function of
$$2 (F_{n+1}^2 +  F_{n+2}^2)$$
and show that they are equal.
\item
Find the generating function for the ways of making change for $n$ cents using
nickles, dimes and quarters satisfying the following conditions:
\begin{enumerate}
\item no restriction
\item there are at most 10 nickles and 10 dimes
\item there are at most 20 nickles and dimes (together)
\item the number of nickles and dimes (together) is even
\item the number of coins (nickles, dimes and quarters) is even\\
\end{enumerate}
If you want to check your answer on the computer to 
that you have the correct generating function then you should find that
to make change for \$13.55 
for condition 
(a) there are 3781 ways;  
(b) there are 24 ways;
(c) there are 46 ways;
(d) there are 1890 ways; 
for condition (e) there are 1877 ways.
\end{enumerate}


\end{document}
