21
$\begingroup$

While solving a problem, I reduced it in the form of the following recurrence relation.

$ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $

However https://en.wikipedia.org/wiki/Catalan_number tells me, this is the recurrence relation for catalan numbers and it can be further simplified as,

$ C_{0} = 1, C_{n} = \displaystyle\frac {2(2n - 1)}{n + 1} C_{n - 1}$

How can I derive the second relationship from the first one ? One way is to prove it is by induction, but we don't know the simplified recurrence so far.

$\endgroup$
  • 1
    $\begingroup$ The last sentence is ungrammatical and unclear. $\endgroup$ – joriki Mar 22 '13 at 13:05
  • $\begingroup$ Getting the last recurrence from the explicit formula is considered cheating? $\endgroup$ – vonbrand Mar 22 '13 at 13:45
  • $\begingroup$ @joriki: I apologize. What I meant was, can we get to the second recurrence relation using only the first recurrence relation ? Assuming we already know the second recurrence relation, we can prove its correctness or we can derive it using closed form as done by MhenniBenghorbal, but what if we only have the first recurrence relation ? $\endgroup$ – Shashwat Mar 22 '13 at 15:44
  • 2
    $\begingroup$ If you don't mind a slight detour, one elegant proof is to show that the number of right-up lattice paths from (0,0) to (n,n) that do not cross over the diagonal satisfies the first recurrence. This is almost natural because we want to find something that decomposes in exactly one way into two parts, which in general are objects of this sort. If we didn't see the relation to lattice paths, we could have thought of valid bracket sequences because the first part can be everything in the first matching pair of brackets and the second part can be everything outside. $\endgroup$ – user21820 Jul 17 '14 at 2:44
  • 1
    $\begingroup$ After that the reflection proof is also natural because when we consider the paths that cross the diagonal they must cross the diagonal for the first time at a unique point that is solely determined by the part of the path before that, and so reflecting the rest of the path will be a bijection to a more easily countable set. $\endgroup$ – user21820 Jul 17 '14 at 2:48
26
$\begingroup$

You can probably find it somewhere online, but for completeness here’s a derivation of the familiar closed form for $C_n$ from the recurrence $$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\tag{0}$$ and the initial value $C_0$, via the ordinary generating function. Then, as in Mhenni Benghorbal’s answer, you can easily (discover and) verify the first-order recurrence. I don’t see any nice way to get it directly from $(0)$.

Let the ordinary generating function for the Catalan numbers be

$$c(x)=\sum_{n\ge 0}C_nx^n=\sum_{n\ge 0}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\;.$$

Then since $C_0=1$, we have

$$\begin{align*} c(x)&=\sum_{n\ge 0}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\\ &=1+\sum_{n\ge 1}\sum_{k=0}^{n-1}C_kC_{n-1-k}x^n\\ &=1+x\sum_{n\ge 0}\sum_{k=0}^nC_kC_{n-k}x^n\\ &=1+x\left(\sum_{n\ge 0}C_nx^n\right)^2\\ &=1+xc(x)^2\;, \end{align*}$$

or $xc(x)^2-c(x)+1=0$. The quadratic formula then yields

$$c(x)=\frac{1\pm\sqrt{1-4x}}{2x}\;,\tag{1}$$

and since

$$\lim_{x\to 0}c(x)=\lim_{x\to 0}\sum_{n\ge 0}C_nx^n=C_0=1\;,$$

it’s clear that we must choose the negative square root in $(1)$, so that

$$c(x)=\frac{1-\sqrt{1-4x}}{2x}\;.$$

Now apply the binomial theorem to $\sqrt{1-4x}$:

$$\begin{align*} \left(1-4x\right)^{1/2}&=\sum_{n\ge 0}\binom{1/2}n(-4x)^n\\ &=\sum_{n\ge 0}\frac{\left(\frac12\right)\left(-\frac12\right)\left(-\frac32\right)\dots\left(-\frac{2n-3}2\right)}{n!}(-4x)^n\\ &=\sum_{n\ge 0}(-1)^{n-1}\frac{(2n-3)!!}{2^nn!}(-4x)^n\\ &=-\sum_{n\ge 0}\frac{2^n(2n-3)!!}{n!}x^n\\ &=-2\sum_{n\ge 0}\frac{2^{n-1}\prod_{k=1}^{n-1}(2k-1)}{n(n-1)!}x^n\\ &=-2\sum_{n\ge 0}\frac{2^{n-1}(n-1)!\prod_{k=1}^{n-1}(2k-1)}{n(n-1)!^2}x^n\\ &=-2\sum_{n\ge 0}\frac{\left(\prod_{k=1}^{n-1}(2k)\right)\left(\prod_{k=1}^{n-1}(2k-1)\right)}{n(n-1)!^2}x^n\\ &=-2\sum_{n\ge 0}\frac{(2n-2)!}{n(n-1)!^2}x^n\\ &=-2\sum_{n\ge 0}\frac1n\binom{2(n-1)}{n-1}x^n\;, \end{align*}$$

where the constant term is $1$ and therefore the constant term in the summation is actually $-\frac12$. Thus,

$$\begin{align*} c(x)&=\frac1{2x}\left(1+2\left(-\frac12+\sum_{n\ge 1}\frac1{n}\binom{2(n-1)}{n-1}x^n\right)\right)\\ &=\sum_{n\ge 1}\frac1n\binom{2(n-1)}{n-1}x^{n-1}\\ &=\sum_{n\ge 0}\frac1{n+1}\binom{2n}nx^n\;, \end{align*}$$

and we have the familiar closed form $C_n=\dfrac1{n+1}\dbinom{2n}n$.

$\endgroup$
  • $\begingroup$ Amazing. If I understood good, it means that $C_n$ is the Catalan sequence if and only if it satisfies this: $C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}$. $\endgroup$ – user67878 Mar 22 '13 at 23:57
  • $\begingroup$ @Thus: That’s right: that initial value and recurrence completely determine the entire sequence of Catalan numbers. $\endgroup$ – Brian M. Scott Mar 23 '13 at 0:02
  • $\begingroup$ Is that true for every sequence generated by this "cauchyproductlike" recurrence if we change the initial value to some other number? $\endgroup$ – user67878 Mar 23 '13 at 0:08
  • 1
    $\begingroup$ @BrianM.Scott In the first half of your answer, how do you go from $1+x\sum_{n\ge 0}\sum_{k=0}^nC_kC_{n-k}x^n$ to $1+x\left(\sum_{n\ge 0}C_nx^n\right)^2$ $\endgroup$ – AlanH Apr 11 '13 at 2:32
  • 2
    $\begingroup$ @Alan: Just multiply out the square: the coefficient of $x^n$ in $$\left(\sum_{n\ge 0}a_nx^n\right)\left(\sum_{n\ge 0}b_nx^n\right)$$ is $$\sum_{k=0}^na_kb_{n-k}\;.$$ $\endgroup$ – Brian M. Scott Apr 11 '13 at 3:36
8
$\begingroup$

A related problem. It is easier to prove it using the identity

$$ C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \implies C_{n-1}=\frac{(2(n-1))!}{(n)!\,(n-1)!} $$

$$ \frac{C_n}{C_{n-1}}= \frac{ (2n)(2n-1)(2n-2)!(n-1)! }{(n+1)n(n-1)!(2n-2)!}=\frac{2(2n-1)}{n+1} $$

$$ \implies C_n = \frac{2(2n-1)}{n+1} C_{n-1}. $$

Added: We will find the ordinary generating function. Let $g(x)=\sum_{n=0}^{\infty}C_{n}x^{n} $

$$ C_{n+1} = \displaystyle\sum_{i=0}^{n } C_{i}C_{n - i } \implies \sum_{n=0}^{\infty}C_{n+1}x^n = \sum_{n=0}^{\infty} \sum_{i=0}^{n } C_{i}C_{n - i } x^n $$

$$ \implies \sum_{n=1}^{\infty}C_{n}x^{n-1} = \sum_{i=0}^{\infty}C_i\sum_{n=i}^{\infty}C_{n-i}x^n= \sum_{i=0}^{\infty}C_i\sum_{n=0}^{\infty}C_{n}x^{n+i}$$

$$\implies \frac{1}{x}\sum_{n=0}^{\infty}C_{n}x^{n}-\frac{C_0}{x}= \sum_{i=0}^{\infty}C_ix^i\sum_{n=0}^{\infty}C_{n}x^{n} $$

$$ \implies \frac{g(x)}{x}-\frac{1}{x} = g(x)g(x) = g(x)^2 $$

$$ \implies g(x)^2-\frac{g(x)}{x}+\frac{1}{x} = 0. $$

$\endgroup$
  • 1
    $\begingroup$ Typo in the second line: first $(n-1)$ is $(n+1)$. But I can't do one-character edits. $\endgroup$ – half-integer fan Mar 22 '13 at 13:54
  • $\begingroup$ @half-integerfan: Thank you. I really appreciate it. $\endgroup$ – Mhenni Benghorbal Mar 22 '13 at 14:00
  • $\begingroup$ @MhenniBenghorbal I used the same method but if we don't know the closed form, we can't get it. Is it possible to get this relation using only the first recurrence relation mentioned in the question ? $\endgroup$ – Shashwat Mar 22 '13 at 15:37
  • $\begingroup$ @Shashwat: But the question you should ask first is how did they get this closed form? $\endgroup$ – Mhenni Benghorbal Mar 22 '13 at 21:07
  • $\begingroup$ @MhenniBenghorbal: I can get the closed form using generating functions for simple cases like f(n) = cf(n - k) or fibonacci etc. But in this case, there are two terms multiplying and summing which made this too complicated for me figure out the closed form. :( $\endgroup$ – Shashwat Mar 22 '13 at 21:20
6
$\begingroup$

Note: This answer is merely a slight variation of the answers already given. The derivation of the generating function of the Catalan Numbers is somewhat different which may be convenient for the reader.

The following is valid: The recurrence relation \begin{align*} C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}\qquad(n\geq 1)\tag{1} \end{align*} specifies the Catalan Numbers \begin{align*} \qquad\qquad\frac{1}{n+1}\binom{2n}{n}\qquad\qquad(n\geq 0)\tag{2} \end{align*}

Note: The connection between the closed formula (2) and the formula stated in the question is given at the beginning of the answer from @MhenniBenghorbal.

Generating function for $C_n$:

When looking at the recurrence relation we see that $\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1}$ is a Cauchy-Product. Since Cauchy products occur when multiplying series it seems natural to work with the following generating functions:

\begin{align*} C(z) = \sum_{n\geq 0}C_nz^n\qquad\text{and}\qquad C^2(z)=\sum_{n\geq 0}\left(\sum_{i=0}^{n}C_iC_{n-i}\right)z^n\tag{3} \end{align*}

Let $[z^n]$ denote the coefficient operator. We observe with the help of (1) and (3):

\begin{align*} [z^n]C(z)&=C_n\\ &=\sum_{i=0}^{n-1}C_iC_{(n-1)-i}\\ &=[z^{n-1}]C^2(z)\\ &=[z^n]zC^2(z)\qquad\qquad\qquad(n\geq 1)\\ \\ [z^0]C(z)&=C_0=1\\ \end{align*}

Therefore we get

\begin{align*} C(z)=zC^2(z)+C_0=zC^2(z)+1 \end{align*}

and solving the quadratic equation gives

\begin{align*} C_{1,2}(z)=\frac{1}{2z}\left(1\pm\sqrt{1-4z}\right) \end{align*} Since the expansion of $\sqrt{1-4z}=1-2z-\ldots$ and $C(z)= \sum_{n\geq 0}C_nz^n$ is a power series in $z$ we conclude that following solution is valid:

\begin{align*} C(z)=\frac{1}{2z}\left(1-\sqrt{1-4z}\right) \end{align*}

Now:

Calculation of $C_n$:

With the help of the well known binomial identity $$\binom{\frac{1}{2}}{n}=\frac{(-1)^{n+1}}{4^n(2n-1)}\binom{2n}{n}$$ we get \begin{align*} C_n&=[z^n]\frac{1}{2z}\left(1-\sqrt{1-4z}\right)\\ &=-\frac{1}{2}[z^{n+1}]\sqrt{1-4z}\\ &=-\frac{1}{2}[z^{n+1}]\sum_{n\geq 0}\binom{\frac{1}{2}}{n}\left(-4z\right)^n\\ &=-\frac{1}{2}\binom{\frac{1}{2}}{n+1}\left(-4\right)^{n+1}\\ &=\frac{1}{2}\frac{1}{2n+1}\binom{2n+2}{n+1}\\ &=\frac{1}{2}\frac{1}{2n+1}\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}\\ &=\frac{1}{n+1}\binom{2n}{n} \end{align*}

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.