\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 3}{Due Mon. March 10, 2025}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines that apply to all homeworks.

\begin{enumerate}

\newcommand{\FF}{F}
\item{} Prove that $\FF_n^2 = \FF_{n-1}\FF_{n+1} + (-1)^n$ for $n\ge 1$.  Manipulate the identity to explain why Lewis Carroll's ``proof'' below that $64 = 65$ (and larger analogues) seems reasonable.
\begin{center}
\begin{tikzpicture}[scale=0.33]
	\begin{scope}[shift={(-10,-4)}]
		\draw[black!30] (0,0) grid (8,8) ;

		\begin{scope}[every path/.style={ultra thick}]
			\draw (0,0) rectangle (8,8) ;
			\draw (5,0) -- (5,8) (5,0) -- (8,8) (0,5) -- (5,3) ;
		\end{scope}
	\end{scope}

	\begin{scope}[shift={(2,-2.5)}]
		\draw[black!30] (0,0) grid (13,5) ;

		\begin{scope}[every path/.style={ultra thick}]
			\draw (0,0) rectangle (13,5) ;
			\draw (0,0) -- (13,5) (8,0) -- (8,3) (5,5) -- (5,2) ;
		\end{scope}
	\end{scope}
\end{tikzpicture}
\end{center}

\item Generating functions.  Let $A(x)$ be the generating function for the Fibonacci sequence $F_n$, with $F_0 = F_1 = 1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\ge 2$.  
\begin{enumerate}
	\item Obtain $A(x)$ from the Fibonacci recurrence.
	\item Obtain $A(x)$ by building it combinatorially (without the recurrence), using the model that $F_n$ is the number of $\{1,2\}$-lists that sum to $n$.
	\item Expand the generating function to prove that $F_n=\sum_{k\ge 0} \binom{n-k}{k}$.
\end{enumerate}

\item {[CM 2.3.8]} In the game ``High/low'', a number is chosen uniformly at random from $[n]$, where $n$ is known.  The player makes a guess, winning the prize of correct.  Otherwise, she learns whether the guess is high or low and guesses again.  When each guess is made randomly from the remaining possible values, the expected numbers of guesses when $n\in\{0,1,2,3\}$ are $0,1,3/2,17/9$, respectively.

The \emph{harmonic number} $H_n$ is defined by $H_n = \sum_{k=1}^n 1/k$.  Obtain a formula for the expected number of guesses made to win the prize, using one harmonic number in the formula.  (Hint: Obtain a recurrence with many terms.  Simplify via natural substitutions and reduce to a first-order recurrence.)

\item Let $s(n)$ be the number of sequences $(x_1,\ldots,x_k)$ of integers satisfying $1\le x_i\le n$ for all $i$ and $x_i\ge 2x_{i-1}$ for $1< i\le k$.  (The length of the sequence is not specified, and the empty sequence is included, and therefore $s(0)=1$.)
\begin{enumerate}
	\item Prove that $s(n)=s(n-1)+s(\floor{n/2})$ for $n\ge 1$.
	\item Let $S(t)=\sum_{n\ge 0} s(n)t^n$, so that $S(t)$ is the generating function for the sequence $\left<s\right>$.  Show that $(1-t)S(t)=(1+t)S(t^2)$.
\end{enumerate}
Medium Challenge: determine good bounds on $s(n)$.

\item Let $a_n$ be the number of domino tilings of a $(2\times n)$-rectangle and let $b_n$ be the number of domino tilings of a $(3\times 2n)$-rectangle.  Obtain bounded order recurrences for $\left<a\right>$ and $\left<b\right>$.  (Medium challenge: find a bounded order recurrence for the number of domino tilings of a $(4\times n)$-rectangle.)

\item {[CM 2.2.34]} The Delannoy numbers satisfy $d_{m,n} = d_{m,n-1} + d_{m-1,n-1} + d_{m-1,n}$ for $m,n\ge 1$ with $d_{m,0} = d_{0,n} = 1$ for $m,n\ge 0$.  Find the generating function $\sum_{m,n\ge 0} d_{m,n}x^my^n$.  Using a clever factorization of the denominator, prove that $d_{m,n} = \sum_k 2^k \binom{m}{k}\binom{n}{k}$.  (Hint: factor $(1-x)(1-y)$ out of the denominator.)

\end{enumerate}
\end{document}
