Solving the Cake Series

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

$c_{m,n} = c_{m,n-1} + c_{m-1,n-1}$

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:

$c_{m,n} = c_{m,n-1} + c_{m-1,n-1}$

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

$f(x,y)=\sum_{i,j=0}^{\infty}c_{i,j} x^i y^j$

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.

\begin{align} f(x,y)&=\sum_{i,j=0}^{\infty}c_{i,j} x^i y^j \\ &=c_{0,0}+\sum_{i=1}^{\infty}c_{i,0} x^i+\sum_{j=1}^{\infty}c_{0,j} y^j + \sum_{i,j=1}^{\infty}c_{i,j} x^i y^j \\ \end{align}

We separate the terms where either $$i$$ or $$j$$ equals $$0$$, since we can write recurrence for $$c_{i,j}$$ iff $$i, j \geq 1$$. For second and third sums above5,

$\sum_{i=1}^{\infty}c_{i,0} x^i = x+x^2+x^3+\dots = \frac{x}{1-x}$

So overall we have

$f(x,y) = 1+\frac{x}{1-x}+\frac{y}{1-y}+\sum_{i,j=1}^{\infty}c_{i,j} x^i y^j$

Now for the last sum, we can apply our recurrence relation

\begin{align} \sum_{i,j=1}^{\infty}c_{i,j} x^i y^j &= \sum_{i,j=1}^{\infty}(c_{i,j-1}+c_{i-1,j-1}) x^i y^j \\ &= \sum_{i,j=1}^{\infty}c_{i,j-1} x^i y^j+\sum_{i,j=1}^{\infty}c_{i-1,j-1} x^i y^j \\ &= y\sum_{i,j=1}^{\infty}c_{i,j-1} x^i y^{j-1}+xy\sum_{i,j=1}^{\infty}c_{i-1,j-1} x^{i-1} y^{j-1}\\ \end{align}

Rearranging the limits and product in the sums so that we can obtain it in the $$f(x,y)$$ form

\begin{align} \sum_{i,j=1}^{\infty}c_{i,j} x^i y^j &= y\sum_{i=1,j=0}^{\infty}c_{i,j} x^i y^{j}+xy\sum_{i,j=0}^{\infty}c_{i,j} x^{i} y^{j}\\ &= y\left(\sum_{i=0,j=0}^{\infty}c_{i,j} x^i y^{j}-\sum_{j=0}^{\infty}c_{0,j}\right)+xy\sum_{i,j=0}^{\infty}c_{i,j} x^{i} y^{j}\\ &= y\left(f(x,y)-\sum_{j=0}^{\infty}c_{0,j}\right)+xyf(x,y)\\ &= y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\ \end{align}

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

\begin{align} f(x,y) &=1+\frac{x}{1-x}+\frac{y}{1-y}+ y\left(f(x,y)-\frac{1}{1-y}\right)+xyf(x,y)\\ (1-y-xy) f(x,y) &= 1+\frac{x}{1-x}+\frac{y}{1-y}-y\left(\frac{1}{1-y}\right)\\ f(x,y) &= \frac{1}{(1-x)(1-y-xy)}\\ \end{align}

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

$\frac{1}{1-x}=1+x+x^2+x^3+\dots$

Also, the second expression is a well known generating function

$\frac{1}{1-y-xy}=\frac{1}{1-y(1+x)}=\sum_{i,j=0}^{\infty}\binom{j}{i} x^i y^j$

So we can view our function in this form as a product

$f(x,y) = (1+x+x^2+x^3+\dots) \left(\sum_{i,j=0}^{\infty}\binom{j}{i} x^i y^j\right)$

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

$\dots + \left(\binom{j}{i}+\binom{j}{i-1}+\dots+\binom{j}{0}\right) x^i y^j + \dots$

Therefore we have (as speculated in previous post)

$c_{i,j} =\binom{j}{i}+\binom{j}{i-1}+\dots+\binom{j}{0} =\sum_{k=0}^{i}\binom{j}{k}$

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)$$.

$\text{Hypercake Number:} ~~ c_{m,n} =\sum_{i=0}^{m}\binom{n}{i}$
1. Hint: $$f(x,y)=\frac{1}{(x-1)(xy+y-1)}$$

2. Proof: \begin{align*} S & = 1 + x + x^2 + x^3 + \cdots\\ \underline{- xS} & \underline{\,\, = ~~ - x - x^2 - x^3 - \cdots}\\ (1-x)S & = 1 \end{align*}