Name:      

Directions: Show all work.

1. Let $U={[n]}^2=\{(x,y):x,y\in \{1,\dots ,n\}\}$.

   1. [4 points] Use $U$ to give a combinatorial proof that $n^2=2\left(\genfrac{}{}{0.0pt}{}{n}{2}\right)+n$.
   2. [3 points] Use part (a) and an identity from HW12 to give a formula for ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^n{k}^2$.
2. [3 points] Let $n$ be a positive integer. Let $A$ be the set of all triples $\{x,y,z\}\in \left(\genfrac{}{}{0.0pt}{}{[n]}{3}\right)$ such that $x<y<z$ and $z-y=y-x$. Let $B$ be the set of all pairs $\{a,b\}\in \left(\genfrac{}{}{0.0pt}{}{[n]}{2}\right)$ such that $a<b$ and $b-a$ is even. Give a bijection to show that $|A|=|B|$.