[Math] What's next?

3) 2, 4, 8,

Let's do the simple one first:

16, 32, 64: it doubles every step

Now the difficult one:

15, 26, 42, 64

Imagine having a three-dimensional, let's say cubical, cake. And you want to divide the cake in as many possible parts with only N cuts.

Let's start with the 2 dimensional case: a square pancake.

The first cut (N=1) divides the pancake in 2 parts.
The second cut (N=2) can divide the pancake in 3 or 4 parts, so the maximum number or parts is 4.

More generally: Imagine we have cut the pancake p-1 times, and we have f(p-1) parts. Now we add a pth cutline, to maximize the number of parts, line p should intersect all other p-1 lines, which causes line p to be divided in p segments. All those p segments divides a part by two, so the new number of parts is:

f(p) = f(p-1) + p


Now the three dimensional case

Imagine we have cut the 3D cake q-1 times, and we have g(q-1) parts. Now we add a qth cutplane, to maximize the number of parts, plane q should intersect all other q-1 planes. Now comes the different part: If we look at plane q, we see a 2 dimensional plane with q-1 cutlines (the intersection of two non-parallel planes is a line) with f(q-1) 2D parts: the solution for the 2 dimensional pancake. Each of them act as a dividing wall of their respective 3D parts, so the new number of 3D parts is:

g(q) = g(q-1) + f(q-1)

with g(0) = f(0) = 1, we get

2, 4, 8, 15, 26, 42, 64...