\documentclass[11pt]{article}
\usepackage{amsmath}  % this adds some math 
\usepackage{fullpage}
\usepackage{tikz}            % if you delete this, you will have trouble with the included picture. You can delete the picture.
\usepackage{chessboard}
\usepackage{hyperref}

% If you have a problem, please let me know sooner than later

\newcommand\name{Chuck Norris} %%%%%%%%%%%%%%  WRITE YOUR NAME HERE



\newcounter{excounter}
\setcounter{excounter}{1}
\newcommand\question[2]{\vskip 1em  \noindent\textbf{\arabic{excounter}\addtocounter{excounter}{1}:} \emph{#1} \noindent#2}


% You can also erase this if you do not have package hancyhdr
% Fancy footnote......... 
\usepackage{fancyhdr}  %% If it does not work with your latex installation, you may just delete this...
\pagestyle{fancy}
\usepackage{lastpage}
\rfoot{\name, page \thepage/\pageref{LastPage}}
\cfoot{}
\rhead{}
\lhead{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}



%%% Note that you do not have to use this template. You can use your own writeup or make any adjustment to this one you like.
%%% This is provided only for your convenience. 


\begin{document}


{\bf MATH304  \hspace{1cm} HW 10\hfill \name}
\vskip 1em

% left column
\begin{minipage}[t]{0.75\textwidth}
Due \textbf{Nov 12} before class, \textbf{answer without justification will receive 0 points}.
The typing the HW in \LaTeX{} is optional. 
\end{minipage}
% right box for score column
\begin{minipage}[t]{0.25\textwidth}
\hfill \begin{tabular}{|r|}
\hline
\hskip 3em Score \hskip 3em \\
\hline \\ \\
\hskip 3em /60 \\
\hline
\end{tabular}
\end{minipage}




\question{}{
Use Fibonacci numbers to count the following problems:
\begin{itemize}
\item[(a)] Count the number of subsets of $\{1,2,\ldots,n\}$ that􏰙 do not have having consecutive integers?
\item[(b)] Count the $n$-digit numbers that contains only digits 1 and 2 and no two adjacent 1s?
\item[(c)] Count the number of ways of walk up $n$ stairs where one step can be to the next step or you can skip one step. 
\end{itemize}
(Hint: Derive a recurrence in each case.)
}

\textbf{Solution:}

\question{}{
Show that consecutive Fibonacci have greatest common divisor one. That is $\gcd(F_n,F_{n-1}) = 1$ for all $n \geq 1$.
In other words, they are relatively prime.
}

\textbf{Solution:}


\question{}{
Prove that Fibonacci numbers satisfy the following identities:
\begin{itemize}
\item[(a)] $3F_n = F_{n+2} + F_{n-2}$  for $n\geq2$.
\item[(b)] $4F_n = F_{n+2} + F_n + F_{n-􏰚2}$ for $n\geq2$.
\end{itemize}
}

\textbf{Solution:}


\question{}{
Find generating functions for the following sequences (and simplify them - i.e. without infinite sums):\\
(a) $0, 0, 0, 4, -4, 4, -4, 4, -4, 4, -4, \ldots$ \\
(b) $1,4,9,16,25,36,49,\ldots$\\
(c) $\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}, \ldots$\\
\emph{Use derivative, integral and/or decomposing one sequence into several simpler ones.}
}

\textbf{Solution:}


\question{}{
Use generating functions to
find the number of solutions to $z_1+z_2+z_3+z_4 = 10$ where the $z_i$ are nonnegative integers
such that $z_1 \leq 4$, $z_2$ is odd, $z_3$ is prime (smallest prime is 2), and $z_4 \in \{1,2,3,6,8\}$.
Use \url{http://wolframalpha.com} to expand the generating function.
}

\textbf{Solution:}


\question{}{
Find coefficient of $x^k$ in the following generating functions:
\begin{itemize}
\item[(a)] $\frac{1}{(1-x)(1-2x)}$
\item[(b)] $\frac{1}{(1-x)(1-x^2)}$
\end{itemize}
}

\textbf{Solution:}






\end{document}














