So I'm trying to solve this problem and I think I'm on the write track, but my proof relies on a domino being divisible by 2, which I don't think is correct.
The problem: Prove that a $2^n \times 2^n$ checkerboard can be covered exactly by dominoes (a domino is a rectangle consisting of two adjacent squares). Give proof by induction.
A checkerboard must always have an identical # of black and white squares in order to be tiled by dominoes. Assume a checkerboard with $N$ squares will always have $N/2$ black squares and $N/2$ white squares, so it can be tiled with dominoes.
My Basis: $P(1)=2^1 \times 2^1 = 4$ squares, giving us 2 black squares and 2 white squares.
Inductive Hypothesis: $P(k) = 2^k \times 2^k$
Need to show: $P(k+1)=2^{k+1} \times 2^{k+1}$
To increase the size of the $2^k \times 2^k$ checkerboard, you need to add 2 squares to both the height and width of the checkerboard. So, $2(2^k) \times 2(2^k)$ is increasing the size of the checkerboard, and will always provide an even number of squares, which creates an identical number of black and white squares on the checkerboard.
$2(2^k) \times 2(2^k) = 2^{k+1} \times 2^{k+1}$
Therefore, a $2^n \times 2^n$ checkerboard can always be tiled by dominoes for any $n\in\mathbb N$.
Is this correct? I feel like I'm all over the place with this proof, and am not sure if having a checkerboard be divisible by 2 actually proves that I'll get an identical number of black and white squares.
Thanks!
HINT: In the figure below, each of the squares $A,B,C$, and $D$ is a $2^k\times 2^k$ checkerboard. How big is the whole board?