Name:      

Directions: Show all work. No credit for answers without work.

1. Prove the following by induction or the no minimum counter-example technique.

   1. [15 points] Recall that ${\widehat{F}}_0={\widehat{F}}_1=1$ and ${\widehat{F}}_n={\widehat{F}}_{n-1}+{\widehat{F}}_{n-2}$ for $n\ge 2$. Prove that ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=0}^n{\widehat{F}}_k={\widehat{F}}_{n+2}-1$ for $n\ge 0$.
   2. [15 points] Prove that for $n\ge 0$, we have ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^n\frac{2k+1}{k^2{(k+1)}^2}=1-\frac{1}{{(n+1)}^2}$.

2. [20 points] Let $n$ be a positive odd integer, and let $G_n$ be the $n\times n$ grid with $n^2$ cells. For $0\le x,y\le n-1$, let $(x,y)$ denote the cell of $G_n$ in column $x$ and row $y$. Let $G_n-(x,y)$ denote $G_n$ with the cell $(x,y)$ removed. Prove that if $x+y$ is odd, then $G_n-(x,y)$ cannot be tiled with dominoes.

      

3. Use the characteristic equation method to solve the following.

   1. [15 points] Find the general solution to the recurrence $a_n=3a_{n-2}+2a_{n-3}$ for $n\ge 3$.
   2. [10 points] Find a closed form formula for $a_n$ with base cases $a_0=a_1=4$ and $a_2=15$.

4. Let $n$ be a positive integer.

   1. [10 points] Give an example of a subset $A$ of $\{1,\dots ,3n\}$ of size $2n$ such that there is no pair $x,y\in A$ with $y-x=n$.
   2. [15 points] Prove that if $A\subseteq \{1,\dots ,3n\}$ and $|A|\ge 2n+1$, then $A$ contains a pair $x,y\in A$ with $y-x=n$.