Title: Use induction to calculate the number of segments in a Sierpinski curve fractal

The post Use induction to calculate the number of segments in a Hilbert curve fractal explains how you can use induction to prove the formula that calculates the size of the Hilbert curve fractal. This post does the same thing for the Sierpinski curve fractal.

The example Draw a Sierpinski curve fractal with Python and tkinter explains how to draw a Sierpinski curve fractal in Python and tkinter. That post says that a Sierpinski curve with depth of recursion D is 2^{D + 2} - 2 segments wide and tall. For example, if you study the picture, you can see that the depth 1 curve is 2^{1 + 3} - 2 = 2³ - 2 = 8 - 2 = 6 segments wide and tall. Similarly the depth 2 curve is 2^{2 + 2} - 2 = 2⁴ - 2 = 16 - 2 = 14 segments wide and tall.

This post explains how you can use induction to prove that. It's actually pretty easy. Let W(N) be the width (and height) of the curve with depth of recursion N.

To prove something by induction, you need to do two things. First, you need to show that it is true for a base case. In this case, you only look at the picture for the depth 1 curve to see that W(1) = 6. Then note that 2^{1 + 2} - 2 = 2³ - 2 = 8 - 2 = 6, so W(N) = 2^{N + 2 - 2 when N = 1.}

The second thing you need to show for induction is that, IF the rule holds true for case N, THEN it must also hold true for case N + 1. In this example, note that a depth N + 1 Sierpinski curve is made up of 4 depth N curves connected by 2 extra segments vertically and horizontally. For example, look at the depth 2 curve shown in the picture. In the picture I've filled the sub-curves with pink and I've filled the area where the sub-curves are connected with blue to make everything easier to see. Note also that all of the vertical and horizontal segments are two divisions wide/tall.

Now look at the depth 2 curve. It's made up of 4 depth 2 curves connected by horizontal and vertical black segments that are 2 divisions long.

That means W(N + 1) = 2 * W(N) + 2. If we assume that the equation holds true for depth N, we know that W(N) = 2^{N + 2} - 2. Plugging that into the equation for N + 1 gives:

W(N + 1) = 2 * W(N) + 2 = 2 * (2^{N + 2} - 2) + 2 = 2 * 2^{N + 2} - 2 * 2 + 2 = 2^{(N + 1) + 2} - 4 + 2 = 2^{(N + 1) + 2} + 2

And that means W(N) = 2^{N + 2} - 2 for all N greater than or equal to 1.