Number of sub-triangles of Divided Equilateral Triangles(DET).

Question

Exercise on Mathematical Induction is from Mathematics for Computer Science by Albert R. Meyer, Eric Lehman, and Frank Thomson Leighton.

1. Divided Equilateral Triangles (DETs) can be built as follows:
   $\bullet$ A single equilateral triangle counts as a DET whose only subtriangle is itself.
   $\bullet$ If $T::= \bigtriangleup$ is a DET, then the equilateral triangle $T'$ built out of 4 copies of $T$ as shown below is also a DET, and the subtriangles of $T'$ are exactly the subtriangles of each of the copies of $T$.

Define the length of a DET to be the number of subtriangles with an edge on its base. Prove by induction on length that the total number of subtriangles of a DET is the square of its length.

Above all, I've noticed that the length of DET doubles each time. However, I can't go further, namely, can't find the way to write induction hypothesis. Please help me to determine induction hypothesis and skeleton of proof.

Answer 1

A DET is an element of the sequence $$T_1,T_2,T_3, ... .$$ where each $T_{n+1}=T_n'$ and $T_1=T$.

The inductive hypothesis is that the number of subtriangles of $T_n$ is the square of its length. This is clearly true for $T_1$.

Suppose the hypothesis to be true for $n=k$.

$T_{k+1}$ is four copies of $T_k$ and so...

its length is twice the length, $l$ say, of $T_k$ and its number of subtriangles is four times the number of subtriangles, $A$ say, of $T_k$. We know that $A=l^2$ and therefore $4A=(2l)^2$.

The hypothesis is therefore true for $k+1$ and so, by induction, is true for all positive integers $n$.