2 Variable Recursion

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$

Solution

First, if $m=n$, then the recursion becomes the recursion of Catalan numbers, and the initial condition $f(0,0) = 1$ matches. So $f(n,n) = C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number.

Our recursion now becomes:

$\displaystyle f(m,n) = \sum_{k=1}^{n} C_{k-1} f(m-k,n-k) + f(m-1,n)$

Let $d = m-n$, we know that the formula holds for $d=0$. For $d>0$, we introduce $g(n,d) = f(n+d,n)$ that is defined over all non-negative $n,d$, with $g(n,0) = C_n \forall n$.

Then our recursion formula becomes:

$\displaystyle g(n,d) = \sum_{k=1}^{n} C_{k-1} g(n-k,d) + g(n,d-1)$

Due to the last term, we also define that $g(n,-1) = 0 \forall n$ to allow that recursion formula to work generally. Note that this convention does not violate the original definition of $f$.

Suppose $P(x) = C_0 + C_1x + C_2x^2 + \cdots + C_nx^n + \cdots$ be an infinite polynomial defined on a region near $x=0$ (within its converging radius). We know that $P(x)$ is the generating function for Catalan numbers, and it's known to be

$\displaystyle P(x) = \frac{1-\sqrt{1-4x}}{2x}$

Now let $Q(x,y) = \sum_{n,d \geq 0} g(n,d)x^ny^d $ also defined near zero.

Consider the coefficient of $x^n y^d $ in $P(x)Q(x,y)$. It is the sum $C_0 g(n,d) + C_1g(n-1,d) + \cdots + C_ng(0,d) = g(n+1,d) - g(n+1,d-1)$

But $\sum_{n \geq 1, d \geq 0}g(n,d)x^ny^d = Q(x,y) - (1+y+y^2 + \cdots) = Q - \frac{1}{1-y}$

Which means the coefficients of $P(x) Q(x,y)$ is identical to $\frac{1}{x}(Q - \frac{1}{1-y}}) - \frac{y}{x}(Q - \frac{1}{1-y})$

$PQ = \frac{1}{x}(Q - \frac{1}{1-y}} )- \frac{y}{x}(Q - \frac{1}{1-y})$ solving for $Q$ yields

$Q(x,y) = \frac{1}{1-y-xP(x)}$

As a sanity check, when $y =0$, all the $y$ terms vanish and $Q$ should be identical to $P$. But since $P$ is the Catalan generating function, it satisfies $P(x) = 1+xP(x)^2$, so $Q = \frac{1}{1-xP} = P$.

One possible approach here is to solve explicitly for $Q(x,y)$ and find its Taylor series to get an explicit formula for $g$ and thus $f$, but it would make you want to gouge your eyes out.

Instead, we note that $P = 1 + xP^2$, so $1-xP = 1-\frac{P-1}{P} = \frac{1}{P}$, thus

$Q=\frac{1}{1-y-xP} = \frac{1}{\frac{1}{P}-y} = \frac{P}{1-Py}$

Which means that $Q-P = yPQ$ is an identity near zero. Note that

$\displaystyle Q-P = \sum_{n \geq 0, d \geq 1}g(n,d)x^ny^d$

And that

$\displaystyle yPQ = \sum_{n \geq 0, d \geq 1}x^ny^d(g(n+1,d-11) - g(n+1,d-2))$

From there we get another identity: $g(n,d) = g(n+1,d-1) - g(n+1,d-2)$ for all $n \geq 0, d \geq 1$

In other words, $g(n,d) = g(n-1,d+1) + g(n,d-1) \forall n\geq 1, d \geq 0$

Translating back, we have $f(m,n) = f(m,n-1) + f(m-1,n)$

Suppose $s = m+n$, we can prove the desired formula by induction on $s$. First, for $m+n=1$, it must be that $m=1,n=0$, and the formula is satisfied trivially. One can also check that the formula still holds for low values of $s$. The induction step holds because:

$f(m,n-1) + f(m-1,n) = \frac{m-n+2}{m+1} \binom{m+n-1}{m} - \frac{m-n}{m} \binom{m+n-1}{m-1}$

$=\frac{n(m-n+2)}{(m+n)(m+1)} \binom{m+n}{m} + \frac{m-n}{m+n} \binom{m+n}{m} = \frac{m-n+1}{m+1} \binom{m+n}{m+1}$