        \problemdata       % Takes 5 *mandatory* arguments
        {vell-tiling}             % latex-friendly label for the prob.
        {induction, tiling}  % The topic(s) of the problem content.
        {Velleman 6.2, problem 6}               % Source (if known)
        {F01 PS2-2} % Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
Velleman 6.2, problem 6.

\solution{
The proof is by induction.

Let P(n) be the proposition that any equilateral triangle, that is cut into 
$4^n$ congruent equilateral triangles with one corner removed, can be tiled 
using tiles composed of three of the smaller congruent triangles.

\textbf{Base case} $n=1$:  With one corner removed, a single tile can be
used to cover the remaining area.
%\mbox{\epsfbox{figures/ps2P5BaseCase.ps}}

\textbf{Inductive step}: Consider a triangle, $T$, cut into $4^{n+1}$
congruent equilateral triangles.  We can think of this triangle as being
cut into four smaller equilateral triangles, which are each then cut into
$4^n$ equilateral triangles.  Remove the top corner of $T$.  We know that
we can tile the triangle that contains the removed corner by the inductive
hypothesis.  Note that the remaining area contains three triangles, who
have corners that meet in the same place; namely, the bottom of T,
directly below the removed corner.  If we consider each of these triangles
with the touching corners removed, then the inductive hypothesis says that
we can tile each one separately.  To complete the tiling, simply use a
single tile to cover the three adjacent removed corners, illustrated in
Figure~\ref{triangle}.

\begin{figure}[ht]
\centering
\includegraphics[width=4in]{figures/ps2P5inductive}
\caption{The original triangle $T$.  Dark lines indicate borders of the four
smaller triangles; light lines indicate borders of the $4^n$ triangles
that the smaller triangles are cut into.  The black triangle is the removed
corner; the gray triangles indicate the corners that are removed from the
smaller triangles in order to apply the inductive hypothesis, which are
then covered by a single tile.}\label{triangle}
\end{figure}
}
\end{problem}