# Solving the Cake Series

In the previous post about hypercake numbers, we obtained a recurrence relation for the hypercake number:

with $c_{m,1} = 2$ and $c_{1,m} = m+1$.

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 $c_{m,0} = 1$ (max cake slices with $0$ cuts) and $c_{0,n} = 1$ (a point cannot be sliced further). Now the new initial conditions are:

with $c_{m,0} = 1$ and $c_{0,n} = 1$.

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

a formal powers series which encodes coefficients of our sequence. To find a generating function for this $f(x,y)$ was not so straightforward3 for me, so I had to seek help from a good samaritan at Math SE4.

We separate the the terms where either $i$ or $j$ equals $0$, since we can write recurence for $c_{i,j}$ iff $i, j \geq 1$. 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 $f(x,y)$ form

Plugging in the last sum $\sum_{i,j=1}^{\infty}c_{i,j} x^i y^j$, in the original definition of $f(x,y)$ we have

Now that we have the generating function of $f(x,y)$, it encodes all of the coefficients compactly.

Notice that in $f(x,y)=\frac{1}{1-x}.\frac{1}{1-y-xy}$ 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 $c_{i,j}$ which will be the same as the coefficient of $x^i y^j$ 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 $c_{m,n}$ which represents the number of maximum pieces a $m$D-hypercake can be sliced into with $n$ cuts made by a slicer of dimension $\geq (m-1)$.

1. Hint: $f(x,y)=\frac{1}{(x-1)(xy+y-1)}$

2. Proof: %