Recurrence relation for Catalan numbers

Question

While trying to find the number of distinct ways we can multiply (parenthesize) n matrices without changing their order (Matrix Chain Multiplication) and using a bottom up approach, I came up with this recurrence relation for Catalan Numbers -

$$T(n) = \binom{n-1}{1}.T(n-1) - \binom{n-2}{2}.T(n-2) + \binom{n-3}{3}.T(n-3) - \binom{n-4}{4}.T(n-4)...$$

or $$\bbox[5px] T(n) = \lvert \sum \limits_{k=1}^{\lfloor n/2 \rfloor} (-1)^{n-k}.\binom{n-k}{k}.T(n-k) \rvert$$

Where T(n) is the nth Catalan Number.

From the Top Down approach and from Wikipedia we get the solution -

$$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\mbox{ for }}n\geq 0.$$

Is it possible to derive one from the other?

For any given set- $$ABCDE$$

Bottom Up approach: Make pairs of 2 matrices and remove the duplicate solutions - $$(AB)CDE,\bbox[5px] A(BC)DE, \bbox[5px]AB(CD)E, \bbox[5px]ABC(DE)$$

Top Down approach: Seperate the set into two distinct sets, no need to remove duplicates - $$(A)(BCDE), \bbox[5px](AB)(CDE), \bbox[5px](ABC)(DE), \bbox[5px](ABCD)(E)$$

Answer 1

If $T(n)$ fulfills $$ T(n) = \sum_{k\geq 1}\binom{n-k}{k}(-1)^{k+1} T(n-k) $$ then $T(n)$ is related with a Chebyshev polynomial of the second kind:

$$ U_n(x) = \sum_{k\geq 0}\binom{n-k}{k}(-1)^k (2x)^{n-2k} $$ and from the generating function for $\{U_n(x)\}_{n\geq 0}$ $$ \sum_{n\geq 0}U_n(x)\,z^n = \frac{1}{1-2x z+z^2} $$ we may find the generating function $\sum_{n\geq 0}T(n)\,z^n=\frac{1-\sqrt{1-4z}}{2z}$ and deduce $$ C_n = \frac{1}{n+1}\binom{2n}{n} $$ from the extended binomial theorem. That is kind of unusual but it works.

Answer 2

We clear up some ambiguities in the post and prove it by strong induction. We let $T(0)=0$ and $T(1)=1$ and prove that when

$$T(n) = \sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k+1} {n-k\choose k} T(n-k)$$

for $n\ge 2$ then $$T(n) = C_{n-1} = \frac{1}{n} {2n-2\choose n-1} = {2n-2\choose n-1} - {2n-2\choose n}.$$

In fact the case of a zero argument to $T$ is not reached as for $n\ge 2$ we also have $n-\lfloor n/2\rfloor \ge 1.$ Applying the induction hypothesis on the RHS we get two pieces, the first is

$$A = \sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k+1} {n-k\choose k} {2n-2k-2\choose n-k-1} \\ = {2n-2\choose n-1} + \sum_{k=0}^{\lfloor n/2\rfloor} (-1)^{k+1} {n-k\choose k} {2n-2k-2\choose n-k-1} $$

and the second

$$B = \sum_{k=1}^{\lfloor n/2\rfloor} (-1)^{k+1} {n-k\choose k} {2n-2k-2\choose n-k} \\ = {2n-2\choose n} + \sum_{k=0}^{\lfloor n/2\rfloor} (-1)^{k+1} {n-k\choose k} {2n-2k-2\choose n-k}.$$

As we subtract $B$ from $A$ we see that we only need to show that the contribution from the two sum terms call them $A'$ and $B'$ is zero.

For these two pieces we introduce the integral representation

$${n-k\choose k} = {n-k\choose n-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2k+1}} (1+z)^{n-k} \; dz.$$

This has the nice property that it vanishes when $k\gt \lfloor n/2\rfloor$ so we may extend the upper limit of the sum to infinity. We also introduce for the first sum

$${2n-2k-2\choose n-k-1} = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n-k}} (1+w)^{2n-2k-2} \; dw.$$

We thus obtain

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} (1+w)^{2n-2} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \sum_{k\ge 0} (-1)^{k+1} \frac{z^{2k} w^k}{(1+z)^k (1+w)^{2k}} \; dz\; dw \\ = - \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} (1+w)^{2n-2} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n} \frac{1}{1+z^2 w/(1+z)/(1+w)^2} \; dz\; dw \\ = -\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} (1+w)^{2n} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{(1+z)(1+w)^2+z^2 w} \; dz\; dw \\ = -\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1+w)^{2n} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{z+1+w} \frac{1}{z + (1+w)/w} \; dz\; dw.$$

We evaluate the inner integral by summing the residues at $z=-(1+w)$ and $z=-(1+w)/w$ and flipping the sign. (We will verify that the residue at infinity is zero.)

The residue at $z=-(1+w)$ yields

$$-\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1+w)^{2n} \\ \times \frac{(-1)^{n+1}}{(1+w)^{n+1}} (-1)^{n+1} w^{n+1} \frac{1}{-(1+w)+(1+w)/w} \; dw \\ = -\frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{n-1} \frac{w}{1-w^2}\; dw.$$

This is zero as the pole at zero has been canceled. Next for the residue at $z=-(1+w)/w$ we get

$$-\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1+w)^{2n} \\ \times \frac{(-1)^{n+1} w^{n+1}}{(1+w)^{n+1}} (-1)^{n+1} \frac{1}{w^{n+1}} \frac{1}{-(1+w)/w+1+w} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1+w)^{n-1} \frac{w}{1-w^2} dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} (1+w)^{n-2} \frac{1}{1-w} dw.$$

With $n\ge 2$ we can evaluate this as $$\sum_{q=0}^{n-1} {n-2\choose q} = 2^{n-2}.$$

To wrap up the residue at infinity of the inner integral is

$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{z+1+w} \frac{1}{z + (1+w)/w} \\ = -\mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{(1+z)^{n+1}}{z^{n+1}} \frac{1}{1/z+1+w} \frac{1}{1/z + (1+w)/w} \\ = -\mathrm{Res}_{z=0} (1+z)^{n+1} \frac{1}{1 + z (1+w)} \frac{1}{1 + z (1+w)/w} = 0.$$

Collecting everything and flipping the sign we have shown that

$$A' = - 2^{n-2}.$$

For piece $B'$ we see that it only differs from $A'$ in an extra $1/w$ factor on the extractor in $w$ at the front. We thus obtain

$$-\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+2}} (1+w)^{2n} \\ \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (1+z)^{n+1} \frac{1}{z+1+w} \frac{1}{z + (1+w)/w} \; dz\; dw.$$

The residue at $z=-(1+w)$ vanishes the same because there was an extra $w$ to spare on the $w/(1-w^2)$ term:

$$-\frac{1}{2\pi i} \int_{|w|=\gamma} (1+w)^{n-1} \frac{1}{1-w^2}\; dw.$$

For the residue at $z=-(1+w)/w$ we are now extracting from

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1+w)^{n-2} \frac{1}{1-w} dw.$$

to get

$$\sum_{q=0}^{n} {n-2\choose q} = 2^{n-2}$$

as before. The residue at infinity vanished in $z$ and did not reach the front extractor in $w$, for another contribution of zero. This means that

$$B' = - 2^{n-2}$$

and we may conclude the proof. The fact that the sum term from the geometric series factored as it did is the remarkable feature of this problem.

Addendum, four years later. In the present version with complex variables the proof requires the convergence of the geometric series. This is $|z^2 w /(1+z)/(1+w)^2 | \lt 1$ or $|z^2 w| \lt |(1+z) (1+w)^2|.$ Now we have $|(1+z) (1+w)^2| \ge (1-\epsilon) (1-\gamma)^2$ so $(1-\epsilon) (1-\gamma)^2 \gt \epsilon^2 \gamma$ will do. Suppose we take $\epsilon = \gamma.$ We obtain $(1-\gamma)^3 \gt \gamma^3.$ Therefore e.g. $\epsilon = \gamma = 1/4$ ensures convergence of the series. This also ensures that the two poles at $-(1+w)$ and $-(1+w)/w$ are outside the contour $|z|=\epsilon.$