building a basis whilst exploring the ocean ...

# Solving the Hypercake Series

In the 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*}