In the previous post about hypercake numbers, we obtained a recurrence relation for the hypercake number:
\[c_{m,n} = c_{m,n1} + c_{m1,n1}\]with \(c_{m,1} = 2\) and \(c_{1,m} = m+1\).
To move forward, some basic understanding of generating functions^{1} and binomial coefficients^{2} 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,n1} + c_{m1,n1}\]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 straightforward^{3} for me, so I had to seek help from a good samaritan at Math SE^{4}.
\[\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 above^{5},
\[\sum_{i=1}^{\infty}c_{i,0} x^i = x+x^2+x^3+\dots = \frac{x}{1x}\]So overall we have
\[f(x,y) = 1+\frac{x}{1x}+\frac{y}{1y}+\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,j1}+c_{i1,j1}) x^i y^j \\ &= \sum_{i,j=1}^{\infty}c_{i,j1} x^i y^j+\sum_{i,j=1}^{\infty}c_{i1,j1} x^i y^j \\ &= y\sum_{i,j=1}^{\infty}c_{i,j1} x^i y^{j1}+xy\sum_{i,j=1}^{\infty}c_{i1,j1} x^{i1} y^{j1}\\ \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}{1y}\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}{1x}+\frac{y}{1y}+ y\left(f(x,y)\frac{1}{1y}\right)+xyf(x,y)\\ (1yxy) f(x,y) &= 1+\frac{x}{1x}+\frac{y}{1y}y\left(\frac{1}{1y}\right)\\ f(x,y) &= \frac{1}{(1x)(1yxy)}\\ \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}{1x}.\frac{1}{1yxy}\) the first term is
\[\frac{1}{1x}=1+x+x^2+x^3+\dots\]Also, the second expression is a well known generating function
\[\frac{1}{1yxy}=\frac{1}{1y(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}{i1}+\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}{i1}+\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\)Dhypercake can be sliced into with \(n\) cuts made by a slicer of dimension \(\geq (m1)\).
\[\text{Hypercake Number:} ~~ c_{m,n} =\sum_{i=0}^{m}\binom{n}{i}\]
http://discrete.openmathbooks.org/dmoi3/sec_countingbinom.html ↩

Hint: \(f(x,y)=\frac{1}{(x1)(xy+y1)}\) ↩

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