Equilateral triangle is cut in $4^n$ congruent equilateral smaller triangles

Question

I have an assignment on proof by induction:

Suppose $n$ is a positive integer. An equilateral triangle is cut into $4^n$ congruent equilateral triangles, and one corner is removed. (Figure $1$ shows an example with $n = 2$). Show that the remaining area can be covered with the trapezoidal tiles of Figure $2$.

Figure $1$

Figure $2$

I have tried to prove it in this way:

1. Base Case:

$n = 1 \rightarrow 4^1$ = $4$

So we have an equilateral triangle with $4$ smaller congruent equilateral triangles. Now, we remove one of them, and we remain with $3$ triangles, which can be occupied by a tile (Figure $2$).

2. Inductive hypothesis:

Let $n$ be arbitrary. Suppose an equilateral triangle is cut into $4^n$ smaller congruent equilateral triangles. We remove $1$ of these smaller triangles, and now we can cover all the big equilateral triangle with $k$ tiles, which is equals to $\frac{4^n - 1}{3}$. Why divided by $3$? Because the tile is composed of 3 smaller congruent equilateral triangles.

3. Inductive step: Assume the point $2$ is true. Let's prove for $n + 1$, so let's suppose that an equilateral triangle is cut into $4^{n+1}$ smaller congruent equilateral triangles, which means $4 * 4^n$ triangles. We know how to fill $4^n$ triangles, so we know also how to fill $1 * 4^n$, right? So we also know how to fill them when they are $2 * 4^n$, $3 * 4^n$ or $4 * 4^n$. Thus, we proved that we can fill an equilateral triangle divided into $4^n$ with those tiles.

I don't think my proof is correct, that's why I am asking your help. Actually, it does not seem even a proof. In particular, if it's wrong, I would like to know why. I did not understand well how to prove by induction yet, so it would be great if you can help me to understand it better!

Answer 1

You suppose $4^n-1=3p$, with $p\in \mathbb{N}$

Then $4^{n+1}-1=4^{n+1}-4+3=4\times(4^n-1)+3=4\times 3p+3=3\times (4p+1)$ ...

Answer 2

You are thinking properly that you assume you can cover the $4^n-1$ case and need to prove you can cover the $4^{n+1}-1$ case. The first point is that in the hypothesis case you don't cover $4^n,$ (and you can't, you have one small triangle left over) you cover $4^n-1$. If you were covering all the small triangles, your approach would be fine-you just cover each of the four triangles the same way you did one for $n$. The one you cut off makes this fail.

What you want to do is to take your solution for $n$ and show there is one for $n+1$. The shape you covered at stage $n$ had a base of $2^n$ segments, sides of $2^n-1$ segments and a top of $1$ segment. If you subdivide each triangle into $4$, you have a shape with a base of $2^{n+1}$ segments, sides of $2^{n+1}-2$, and a top of $3$ segments. Each shape of three triangles becomes $12$ triangles. The below figure shows how to cover the area that was covered by each set of three triangles with four of the smaller sets. Now put one more shape on the top and you have covered the whole $n+1$ order shape.

Answer 3

For the induction step divide the $4^{n+1}$-triangle into four $4^n$-triangles in the obvious way. At the center of the base three of these $4^n$-triangles meet. Put one of your tiles there, and you are done.

Answer 4

A hint in the form of a picture. This illustrate how to construct a $n = 3$ tiling from a $n=2$ one.