Midpoint displacement algorithm is an actual algorithm used for landscape generation. This task shows however, a very real problem which arises in practical use. After ~16~ iterations the number of vertices exceeds ~2^{32}~, even if no duplicates are stored (and doing this actually complicates the rendering process). If each vertex stores only its 3D coordinates as 3 doubles, after ~16~ iterations more than 100 GB of memory is needed to store the landscape alone, with no colour, texture or shade data.

To solve this task, we reduce it to a subproblem. First note that the total number of vertices will always be the square of number of vertices in the first row (or column). If we can determine this number, obtaining the total is simple.

If we look at a single step, starting with ~X~ vertices, midpoint displacement will add one vertex between each of the two neighbouring vertices. Since there are ~X-1~ neighbours, we add ~X-1~ new vertices so at the end of the step we now have ~2X-1~ vertices in total. This leads to a recursive formula where ~N_i~ denotes the number of vertices after ~i~ steps:

$$\displaystyle N_i = 2N_{i-1}-1 \quad \forall i > 0$$

With the special case of ~N_0 = 2~. Using induction, we can prove that the number of vertices in the first row (or column) after ~x~ steps is ~N_x = 2^x+1~.