Solving multivariate generating functions

December 26, 2022
Útulek Series, 6 | CF1761D Chapter, 6

It seemed appropriate to broach the subject directly today—that is, generating functions. To do this, we will be looking at three functions today: $f(x)$ the Fibonacci sequence generating function, $p(x,y)$ the generating function for Pascal’s triangle, and finally $g(x,y)$ the generating function for 1761D: $G_{i,j}=3G_{i-1,j}+3G_{i-1,j-1}-8G_{i-2,j-1}$ (it is minor, but I have since determined that $G$ is a better letter to use than $A$ for 1761D), which, as a reminder, generates

$$\begin{matrix} 1\\ 3&1\\ 9&4&3\\ 27&15&13&9\\ 81&54&52&42&27\\ \ldots. \end{matrix}$$

1 Deriving the Generating Functions

As in the proof for $\zeta(2)$ in Taylor Series, we utilize the properties of a polynomial to gain more information on its coefficients. The theory of generating functions begins by assigning the sequence as the coefficients of the polynomial:

$$\begin{aligned} f(x)&=0x^0+1x^1+1x^2+2x^3+3x^4+5x^5+\ldots\\ &=\sum_i F_ix^i,\\ p(x,y)&=1x^0y^0\\ &+1x^1y^0+1x^0y^1\\ &+1x^2y^0+2x^1y^1+1x^0y^2\\ &+1x^3y^0+3x^2y^1+3x^1y^2+1x^0y^3\\ &+\ldots\\ &=\sum_i\sum_j P_{i,j}x^iy^j,\\ g(x,y)&=1x^0y^0\\ &+3x^1y^0+1x^0y^1\\ &+9x^2y^0+4x^1y^1+3x^0y^2\\ &+27x^3y^0+15x^2y^1+13x^1y^2+9x^0y^3\\ &+\ldots\\ &=\sum_i\sum_j G_{i,j}x^iy^j. \end{aligned}$$

We then proceed to reduce the generating function into a recurrent form for easier analysis. This is quite trivial for one-dimensional recurrences, but two-dimensional ones need some care around boundary conditions. As

$$\begin{aligned} F_i&:=F_{i-1}+F_{i-2},\\ P_{i,j}&:=P_{i-1,j}+P_{i-1,j-1},\\ G_{i,j}&:=3G_{i-1,j}+3G_{i-1,j-1}-8G_{i-2,j-1}, \end{aligned}$$

we have recurrent generating functions

$$\begin{aligned} f(x)&=x+xf(x)+x^2f(x),\\ p(x,y)&=1+xp(x,y)+xyp(x,y),\\ g(x,y)&=1-2xy+3xg(x,y)+3xyg(x,y)-8x^2yg(x,y), \end{aligned}$$

which subsequently solves as

$$\begin{aligned} f(x)&=\frac{x}{1-x-x^2},\\[3ex] p(x,y)&=\frac{1}{1-x-xy},\\[3ex] g(x,y)&=\frac{1-2xy}{1-3x-3xy+8x^2y}. \end{aligned}$$

2 Solving the Fibonacci

I believe all one-degree one-dimensional generating functions may be partial fraction decomposed (this seems easy to prove):

$$\begin{aligned} f(x)&=\frac{x}{1-x-x^2}\\[3ex] &=\frac{(-1-1/\sqrt{5})/2}{x-(-1-\sqrt{5})/2}+\frac{(-1+1/\sqrt{5})/2}{x-(-1+\sqrt{5})/2}\\[3ex] &=\frac{(1+1/\sqrt{5})/2}{(-\sqrt{5}-1)/2-x}+\frac{(1-1/\sqrt{5})/2}{(\sqrt{5}-1)/2-x}\\[3ex] &=\frac{-1/\sqrt{5}}{1-(\sqrt{5}-1)x/2}+\frac{1/\sqrt{5}}{1-(\sqrt{5}+1)x/2}\\[3ex] &=\frac{1}{\sqrt{5}}(\frac{1}{1-(\sqrt{5}+1)x/2}-\frac{1}{1-(\sqrt{5}-1)x/2})\\ \end{aligned}$$

which is now the sum of two geometric sequences in $x$. We may take the coefficient of $x^i$ then as

$$\begin{aligned} F_i=[x^i]f(x)=\frac{1}{\sqrt{5}}((\frac{\sqrt{5}+1}{2})^i+(\frac{\sqrt{5}-1}{2})^i) \end{aligned}$$

which coincides with Binet’s formula as expected.

3 Solving the Pascal

This one was very tricky for me but I ended up solving it at the end of the day.

The key here is sequential isolation of the variable powers with liberal use of geometric series reinterpretations. Of course, one should expect combinatorial arguments to arise at some point. We use $[x]$ to denote “the coefficient of $x$.”

$$\begin{aligned} p(x,y)&=\frac{1}{1-x-xy}=\frac{1}{1-x}\cdot\frac{1}{1-\frac{x}{1-x}y},\\[3ex] [y^j]p(x,y)&=\frac{1}{1-x}\cdot(\frac{x}{1-x})^j,\\[3ex] P_{i,j}=[x^i][y^j]p(x,y)&=[x^i](1+x+x^2+\ldots)(x+x^2+x^3+\ldots)^j\\ &=[x^{i-j}](1+x+x^2+\ldots)^{j+1} \end{aligned}$$

at which point we must use stars and bars with $i-j$ stars and $j$ bars:

$$\begin{aligned} P_{i,j}&=\frac{(i-j+1)(i-j+2)\cdots(i)}{j!}\\[3ex] &={i\choose j}. \end{aligned}$$

The reason radicals don’t show up here is likely to due with the degrees of the variables and the dimension of the recurrence. It has to do with how simple the second term $1/(1-\frac{x}{1-x}y)$ is. I think there’s some simple condition that I’m missing here, but I will sleep on it.

4 Solving 1761D

Similarly,

$$\begin{aligned} g(x,y)&=\frac{1-2xy}{1-3x-3xy+8x^2y}\\[3ex] &=\frac{1}{1-3x}\cdot\frac{1-2xy}{1-\frac{3x-8x^2}{1-3x}y},\\[3ex] [y^j]g(x,y)&=\frac{1}{1-3x}\cdot(\frac{3x-8x^2}{1-3x})^{j-1}(\frac{3x-8x^2}{1-3x}-2x)\\[3ex] &=\frac{1}{1-3x}\cdot(3x+\frac{x^2}{1-3x})^{j-1}(\frac{x-2x^2}{1-3x})\\[3ex] &=x^j\cdot\frac{1}{1-3x}\cdot(3+\frac{x}{1-3x})^{j-1}(1+\frac{x}{1-3x}),\\[3ex] G_{i,j}&=[x^i][y^j]g(x,y)\\[3ex] &=[x^{i-j}](1+3x+9x^2+\ldots)(3+x+3x^2+9x^3+\ldots)^{j-1}(1+x+3x^2+9x^3+\ldots)\\[3ex] &=\sum_{k=0}^{j-1}3^k{j-1\choose k}[x^{i-j}](1+3x+9x^2+\ldots)(x+3x^2+9x^3+\ldots)^{j-1-k}(1+x+3x^2+9x^3+\ldots)\\[3ex] &=\sum_{k=0}^{j-1}3^k{j-1\choose k}[x^{i-2j+1+k}](1+3x+9x^2+\ldots)^{j-k}(1+x+3x^2+9x^2+\ldots)\\[3ex] &=\sum_{k=0}^{j-1}3^k{j-1\choose k}([x^{i-2j+1+k}](1+3x+9x^2+\ldots)^{j-k}+[x^{i-2j+k}](1+3x+9x^2+\ldots)^{j-k+1})\\[3ex] &=\sum_{k=0}^{j-1}3^k{j-1\choose k}(3^{i-2j+1+k}{i-j\choose j-k-1}+3^{i-2j+k}{i-j\choose j-k})\\[3ex] &=\sum_{k=0}^{j-1}3^{i-2j+2k}{j-1\choose k}(3{i-j\choose j-k-1}+{i-j\choose j-k}).\\[3ex] \end{aligned}$$

A quick sanity check has

$$\begin{aligned} G_{3,2}&=3^{-1}{1\choose 0}(3{1\choose 1}+{1\choose 2})+3{1\choose 1}(3{1\choose 0}+{1\choose 1})\\[3ex] &=1+12=13 \end{aligned}$$

as desired.

Note additionally that this form,

$$G_{i,j}=\sum_{k=0}^{j-1}3^{i-2j+2k}{j-1\choose k}(3{i-j\choose j-k-1}+{i-j\choose j-k}),\tag{4.1}$$

is much more natural than either of the forms provided in 2D Recurrences and Combinatorial Arguments, either

$$G_{i,j}=\sum_{k=1}^j{(3^{i-2k}{i-j\choose k}+3^{i-2k+1}{i-j\choose k-1}){j-1\choose k-1}}$$

which only applies to $j\geq 1$ and must have $3^{i-2k}$ zeroed out when $2k>i$, or alternatively, also from the same post,

$$G_{i,j}=\sum_{k=1}^{2j}{3^{i-k}{i-j\choose \lfloor k/2\rfloor}{j-1\choose \lceil k/2\rceil-1}}$$

which has floor and ceiling functions out of nowhere and likewise also only applies for $j\geq 1$.

The form of solutions to two-dimensional recurrences must be intimately related to its order and degree. I intend to explore this relationship briefly in the future.