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

\newcommand{\kgmcomment}[1]{}
\renewcommand{\emptyset}{\varnothing}
\DeclareMathOperator{\cprod}{\Box}

\begin{document}
\headers{Math571}{Homework 2}{Due Feb. 21, 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.

\begin{enumerate}

\item{} Prove the first three identities below by counting a set in two ways.  In each case, give a single direct argument without manipulating the formulas.  In part (d), find a closed form solution for the sum and give a combinatorial proof.
\begin{multicols}{2}
\begin{enumerate}
	\item $\displaystyle \binom{2n}{n} = 2\binom{2n-1}{n-1}$
	\item $\displaystyle \sum_k \binom{k}{l}\binom{n}{k} = \binom{n}{l}2^{n-l}$
	\item $\displaystyle \sum_{i=1}^n i(n-i) = \sum_{i=1}^n \binom{i}{2}$
	\item $\displaystyle \sum_{j=1}^m (m-j)2^{j-1}$
\end{enumerate}
\end{multicols}

\item The graph $P_n \cprod P_3$ is the \emph{Cartesian product} of the $n$-vertex path and the $3$-vertex path; it has vertex set $\{(x,y)\st \mbox{$x\in [n]$ and $y\in [3]$}\}$ with $(x,y)$ and $(x',y')$ adjacent if and only if (1) $x=x'$ and $|y-y'| = 1$, or (2) $|x-x'| = 1$ and $y=y'$.  An \emph{independent set} is a set of pairwise non-adjacent vertices.  

Let $s_0 = 1$ and for $n\ge 1$, let $s_n$ be the number of independent sets in $P_n \cprod P_3$.  Let $X=\{(n,1),(n,2),(n,3)\}$; these are the vertices in the last column of $P_n \cprod P_3$.  For $n\ge 1$, let $a_n$, $b_n$, $c_n$, and $d_n$ be the number of independent sets $S$ in $P_n \cprod P_3$ such that $S\cap X$ equals $\emptyset$, equals $\{(n,1)\}$ or $\{(n,3)\}$, equals $\{(n,2)\}$, or equals $\{(n,1),(n,3)\}$, respectively.  Also, let $x_n$ be the column vector $[a_n~b_n~c_n~d_n]^T$ for $n\ge 1$, and for convenience define $x_0 = [a_0~b_0~c_0~d_0]^T = [1~0~0~0]^T$.  
\begin{enumerate}
	\item Find a $4\times 4$-matrix $A$ such that $x_n = Ax_{n-1}$ for $n\ge 1$.
	\item Using that $s_n = [1~1~1~1] x_n = [1~1~1~1] A^n x_0$, find row vectors $z_0,\ldots,z_4$ such that $s_{n+j} = z_j x_n$ for $0\le j\le 4$.
	\item Let $B$ be the $5\times 4$-matrix with rows $z_0, \ldots, z_4$.  Find a nonzero row vector $y$ such that $yB = 0$.
	\item Using that $yBx_n = 0$, find a $4$th order homogeneous linear recurrence for $s_n$.
\end{enumerate}

\item By pairing positive and negative contributions, give a combinatorial proof for 
\[ \sum_{k=0}^n (-1)^k\binom{n}{k}^2 = \begin{cases}
	0 & \mbox{if $n$ is odd} \\
	(-1)^{n/2} \binom{n}{n/2} & \mbox{if $n$ is even}
\end{cases}.\]

\item Give a combinatorial proof for the following identity by devising a set that both sides count.
\[ \sum_{k\ge 1} k\binom{m+1}{r+k+1} = \sum_{i=1}^m i2^{i-1}\binom{m-i}{r} \]

\item The line segments from $(j,\ln j)$ to $(j+1,\ln(j+1))$ lie below the curve $y=\ln x$ (since $f(x)=\ln x$ is convex).  By comparing the area under the segments from $j=1$ to $j=n$ with the area under the curve $y=\ln x$ from $x=1$ to $x=n+1$, show that $n!\le e\sqrt{n+1}(n/e)^n$.  [Hint: use that $1+x\le e^x$ for real $x$.]

\item{} Flags on poles.
\begin{enumerate}
\item Obtain a simple formula for the number of ways to put $m$ distinct flags on a row of $r$ flagpoles.  Poles may be empty, and changing the order of flags on a pole changes the arrangement.  The formula must only use one ``$m$'' and one ``$r$''.  (The answer is 6 for $m=r=2$, as shown below.)
\newcommand{\drawemptypole}
{
	\draw (0,0) -- (0, 5) ;
}
\newcommand{\drawoneflag}[1]
{
	\drawemptypole
	\node[draw,rectangle,anchor=south west,minimum width=0.95cm,minimum height=0.5cm] at (0, 1) {#1} ;
}
\newcommand{\drawtwoflags}[2]
{
	\drawoneflag{#1}
	\node[draw,rectangle,anchor=south west,minimum width=0.95cm,minimum height=0.5cm] at (0, 3) {#2} ;
}
\newcommand{\drawpairpoles}[2]
{
	\draw (-3,0) -- (5,0) ;
	\begin{scope}[shift={(-2,0)}]
		#1
	\end{scope}
	\begin{scope}[shift={(2,0)}]
		#2
	\end{scope}
}
\begin{center}
\begin{tikzpicture}[scale=0.40]
	\foreach \n/\leftfl/\rightfl in {
						1/\drawtwoflags{1}{2}/\drawemptypole,
						2/\drawtwoflags{2}{1}/\drawemptypole,
						3/\drawoneflag{1}/\drawoneflag{2}
					}
	{
		\begin{scope}[shift={(12*\n,0)}]
			\drawpairpoles{\leftfl}{\rightfl}
		\end{scope}
	}

	\begin{scope}[shift={(0,-7)}]
		\foreach \n/\leftfl/\rightfl in {
						1/\drawemptypole/\drawtwoflags{1}{2},
						2/\drawemptypole/\drawtwoflags{2}{1},
						3/\drawoneflag{2}/\drawoneflag{1}
					}
		{
			\begin{scope}[shift={(12*\n,0)}]
				\drawpairpoles{\leftfl}{\rightfl}
			\end{scope}
		}
	\end{scope}
\end{tikzpicture}
\end{center}
\item Prove that the identity below for rising factorials holds for all $x,y\in \R$.
\[ (x+y)^{(n)} = \sum_k \binom{n}{k}x^{(k)}y^{(n-k)} \]
\end{enumerate}



\end{enumerate}
\end{document}
