Prove, using the well-ordering principle, that, for all $n\geq 1$, an $\mathsf{L}$-shaped space with two sides of length $2n$ and four sides of length $n$ can be tiled using some number of 3 square $\mathsf{L}$-shaped tiles (i.e. with two sides of length 2 and four sides of length 1).
I can prove this by induction, but I'm not sure how to prove it by the well-ordering principle. How do I show this by the well-ordering principle?
On
It’s basically the same argument. For $n\in\Bbb Z^+$ let $L_n$ be the $L$-shaped piece described in the question. Let $B=\{n\in\Bbb Z^+:L_n\text{ cannot be tiled}\}$. You want to show that $B=\varnothing$. Assume, to get a contradiction, that $B\ne\varnothing$. $\Bbb Z^+$ is well-ordered, so $B$ has a least element $n$. Use the basis step of your induction argument to show that $n>1$. Then use the induction step of your induction argument to show that in fact $L_n$ can be tiled, thereby getting a contradiction.
Let $$P=\{n\in\mathbb{N}\mid n\text{ is a counterexample to the claim}\}.$$ The well-ordering principle implies that, if $P$ is non-empty, then there is a minimum element of $P$. Assuming that $P$ is non-empty, let's call the minimum element $m$. Usually one then proceeds in the same way as one would by induction: since $m$ is the smallest element of $P$, we know that $m-1$ is not in $P$, i.e. that the claim is true for $m-1$, and there is some way of using this to demonstrate that $m$ would have to be an element of $P$ as well, which is a contradiction. Thus, our initial assumption that $P$ was non-empty must have been false.