Proof for domino tiling over $m \times n$ checkerboard Prove: For what arbitrary $m \times n$ dimensions of rectangular checkerboards can be tiled by $1 \times 2$ dominos (dominos can be horizontal and vertical). 
My proof states so far that for all $m$ and $n \geq1$, with either $m$ or $n$ as even, the checkerboard of $m \times n$ dimensions can be tiled by horizontal and/or vertical domino tiles. However, I'm having trouble proving this and coming up with a base case and inductive case.
 A: Without loss of generality, let the even number be the width.
Apply double-induction
First Induction hypothesis: any $n\times 2$ grid can be filled regardless the value of $n$.
Base case: $n=1$, i.e. a $1\times 2$ grid.  Clearly it can be filled.
First induction step: Supposing that an $n\times 2$ grid can be filled., we try to fill an $(n+1)\times 2$ grid.  Clearly this is doable by filling the $n\times 2$ grid and then placing one additional tile on top of the rest.  Hence, any $n\times 2$ grid can be tiled for any value of $n$.
Second induction hypothesis: any $n\times (2m)$ grid can be filled for any value of $m$ given a specific value of $n$
Base case: $m=1$, i.e. an $n\times 2$ grid.  This was proven in the previous step.
Second induction step: Supposing that an $n\times (2m)$ grid can be filled., we try to fill an $n\times (2(m+1))$ grid.  This can be accomplished by filling an $n\times (2m)$ grid first and filling the remaining $n\times 2$ grid.
These two steps together prove that any $n\times (2m)$ grid can be tiled regardless the value of $n$ and regardless the value of $m$, hence any grid with even width can be tiled.  By symmetry any grid with even height and not necessarily even width will also be able to be tiled.
Finally, we can look to the case that both height and width are odd.  As there are an odd number of spaces and any tiling will cover only an even number of spaces, there can be no proper tiling, thus proving that it is both a necessary and sufficient condition that for there to be a tiling there must be at least one of the sides of even length.
