In the previous post about hypercake numbers, we obtained a recurrence relation for the hypercake number:
with and .
To move forward, some basic understanding of generating functions1 and binomial coefficients2 is required. For the sake of completeness and simplifying things let us also consider the case of 0 cuts which yield (max cake slices with cuts) and (a point cannot be sliced further). Now the new initial conditions are:
with and .
One way to go about this and generally about solving recurrence relations is to use generating functions, in our case, it will lead to a generating function in two variables. Let’s suppose we have
We separate the the terms where either or equals , since we can write recurence for iff . For second and third sums above5,
So overall we have
Now for the last sum, we can apply our recurrence relation
Rearranging the limits and product in the sums so that we can obtain it in the form
Plugging in the last sum , in the original definition of we have
Now that we have the generating function of , it encodes all of the coefficients compactly.
Notice that in the first term is
Also, the second expression is a well known generating function
So we can view our function in this form as a product
Coming to the showdown we need to find the value of which will be the same as the coefficient of is in the above product. It is not hard to see that it will be
Therefore we have (as speculated in previous post)
Finally the Hypercake Numbers which represents the number of maximum pieces a D-hypercake can be sliced into with cuts made by a slicer of dimension .