Prove area of Koch snowflake by mathematical induction

discrete mathematicsfractalsinduction

Here is an interesting construction of a geometric object known as the Koch snowflake.
Define a sequence of polygons $S_0$, $S_1$ recursively, starting with $S_0$ equal to an equilateral triangle with unit sides. We construct $S_{n+1}$ by removing the middle third of each edge of $S_n$ and replacing it with two line segments of the same length.

Let $a_n$ be the area of $S_n$. Observe that $a_0$ is just the area of the unit equilateral triangle which by elementary geometry is $\frac{\sqrt{3}}{4}$

Prove by induction that for all $n \geq 0$, the area of the nth snowflake is given by:
$$a_n = a_0\left(\frac{8}{5} – \frac{3}{5} \left(\frac{4}{9}\right)^n\right).$$

Best Answer

I want to post the solution, since someone might need it.

Proof. by ordinary induction. Let Induction hypothesis $P(n)$ be $$a_n = a_0\left(\frac{8}{5} - \frac{3}{5}\cdot \left(\frac{4}{9}\right)^n\right).$$ Base case $(n=0):$ $a_0=a_0\left(\frac{8}{5} - \frac{3}{5}\cdot \left(\frac{4}{9}\right)^0\right) = a_0.$ holds.

Inductive step: Assume $P(n)$ holds for some $n \geq 0$. Show that $P(n) \Rightarrow P(n+1).$ We need to show $$a_{n+1} = a_0\left(\frac{8}{5} - \frac{3}{5}\cdot\left(\frac{4}{9}\right)^{n+1}\right).$$ We can write $$a_{n+1} = a_n + e_n t_{n+1}$$ where $e_n = 3\cdot4^n$ and $t_{n+1} = \frac{a_0}{9^{n+1}}.$ Replacing $e_n$ and $t_{n+1}$ in the equation of $a_{n+1}$ gives $$a_{n+1} = a_n + 3\cdot4^n\cdot\left(\frac{a_0}{9^{n+1}}\right)=$$ $$a_n + 3\cdot\left(\frac{1}{9}\right)\cdot a_0\cdot\left(\frac{4^n}{9^{n}}\right)=$$ $$a_n + \frac{1}{3}\cdot a_0\cdot\left(\frac{4}{9}\right)^n=$$ Since P(n) holds, we can replace $a_n$ with $a_0\left(\frac{8}{5} - \frac{3}{5}\cdot\left(\frac{4}{9}\right)^n\right).$ $$a_0\left(\frac{8}{5} - \frac{3}{5}\cdot\left(\frac{4}{9}\right)^n\right) + \frac{1}{3}\cdot a_0\cdot\left(\frac{4}{9}\right)^n=$$ $$a_0\cdot \left(\frac{8}{5}\right) - a_0\cdot \left(\frac{3}{5}\right)\cdot\left(\frac{4}{9}\right)^n + \frac{1}{3}\cdot a_0\cdot\left(\frac{4}{9}\right)^n=$$ $$a_0\cdot \left(\frac{8}{5}\right) - a_0\cdot\left(\frac{4}{9}\right)^n \left(\frac{3}{5} - \frac{1}{3}\right)=$$ $$a_0\cdot \left(\frac{8}{5}\right) - a_0\cdot\left(\frac{4}{9}\right)^n \cdot \left(\frac{4}{15}\right)=$$ $$a_0\cdot \left(\frac{8}{5}\right) - a_0\cdot\left(\frac{4}{9}\right)^n \cdot \left(\frac{4}{9} \cdot \frac{3}{5}\right)=$$ $$a_0\cdot \left(\frac{8}{5}\right) - a_0\cdot\left(\frac{4}{9}\right)^{n+1} \cdot \frac{3}{5}=$$ $$a_0\cdot \left(\frac{8}{5} - \frac{3}{5} \cdot \left(\frac{4}{9}\right)^{n+1}\right)$$ which proves $P(n+1).$

We can conclude, by induction principle, $\forall n \geq 0: P(n)$.