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

The example Draw a Hilbert curve fractal with Python and tkinter explains how to draw a Hilbert curve fractal in Python and tkinter. That post says that a Hilbert curve with depth of recursion D is 2^D - 1 segments wide and tall. For example, if you study the picture, you can see that the depth 3 curve is 2³ - 1 = 8 - 1 = 7 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) = 1. Then note that 2¹ - 1 = 2 - 1 = 1, so W(N) = 2^N - 1 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 Hilbert curve is made up of 4 depth N curves connected by a single extra segment vertically and horizontally. For example, look at the depth 3 curve shown in the picture. That curve is made up of 4 red depth 2 curves connected by thin black segments.

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

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

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