Show that it is the solution of the recurrence

Question

I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$ is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$

I used induction to show that.

I have done the following:

For $n=0$ : $X(1)=1 \checkmark $

We assume that it stands for each $1 \leq k \leq n$: $$X(k)=\frac{1}{k}\binom{2(k-1)}{k-1} \ \ \ \ \ (*)$$

We want to show that it stands for $n+1$:

$$X(n+1)=\sum_{i=1}^{n} X(i)X(n+1-i)=\sum_{i=1}^{n} \frac{1}{i}\binom{2(i-1)}{i-1}\frac{1}{n+1-i}\binom{2(n-i)}{n-i}=\sum_{i=1}^{n}\frac{1}{i}\frac{(2(i-1))!}{(i-1)!(2(i-1)-(i-1))!}\frac{1}{n+1-i}\binom{(2(n-i))!}{(n-1)!(2(n-i)-(n-i))!}=\sum_{i=1}^{n}\frac{(2(i-1))!}{i!(i-1)!}\frac{(2(n-i))!}{(n-i+1)!(n-i)!}$$

How could I continue??

Answer 1

These are the Catalan numbers.

This can be done by generating functions which is quite simple. Set $X_0=0$ and $X_1=1$ and introduce $$f(w) = \sum_{n\ge 0} X_n w^n.$$

Because $X_0=0$ we can extend the recurrence to $$X_n = \sum_{q=0}^n X_q X_{n-q}$$ for $n>1.$

This says that, again for $n>1,$ $$[w^n] f(w) = [w^n] f(w)^2.$$

Multiply by $w^n$ and sum over $n>1$ to get $$\sum_{n\gt 1} w^n [w^n] f(w) = \sum_{n\gt 1} w^n [w^n] f(w)^2.$$

This is an annihilated coefficient extractor (ACE) and it simplifies to $$f(w) - X_1 w - X_0 = f(w)^2 - 2X_0 X_1 w - X_0$$ which is $$f(w) - w = f(w)^2.$$

Solve the quadratic and pick the proper solution to finally obtain $$f(w) = \frac{1}{2} - \frac{\sqrt{1-4w}}{2}.$$

We can extract coefficients from this in various ways, by table lookup or using Lagrange inversion. The Newton binomial series gives $$[w^n] \sqrt{1-w} = (-1)^n {1/2 \choose n} \\ = (-1)^n \frac{1/2 \times (-1/2) \times (-3/2) \times \cdots \times }{n!} = (-1)^n \frac{1}{2^n n!} \times (-1)^{n-1} \prod_{k=0}^{n-2} (2k+1) \\ = - \frac{1}{2^n n!} \frac{(2n-3)!}{\prod_{k=1}^{n-2} (2k)} = - \frac{1}{2^n n!} \frac{(2n-3)!}{2^{n-2} (n-2)!} = - \frac{1}{2^{2n-1} (n-1)} {2n-2\choose n-2}.$$

The conclusion is that $$[w^n] f(w) = \frac{1}{2^{2n} (n-1)} 4^n {2n-2\choose n-2} = \frac{1}{n-1} {2n-2\choose n-2}.$$

Re-write this as $$\frac{1}{n-1} \frac{n-1}{n} {2n-2\choose n-1} = \frac{1}{n} {2n-2\choose n-1}$$ which also holds for $n=1.$

The ACE technique is also used at this MSE link.

Answer 2

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{{\rm X}\pars{1} = 1\,,\qquad\mbox{and}\qquad {\rm X}\pars{n} = \sum_{i\ =\ 1}^{n - 1}{\rm X}\pars{i}{\rm X}\pars{n - i}\,, \quad\mbox{for}\quad n\ >\ 1}$.

Lets $\ds{{\cal X}\pars{z} \equiv \sum_{n\ =\ 1}^{\infty}{\rm X}\pars{n}z^{n}}$, with $\ds{\verts{z} < {1 \over 4}}$, such that \begin{align} {\cal X}\pars{z}&={\rm X}\pars{1}z + \sum_{n\ =\ 2}^{\infty}{\rm X}\pars{n}z^{n} =z + \sum_{n\ =\ 2}^{\infty}\sum_{i\ =\ 1}^{n - 1} {\rm X}\pars{i}{\rm X}\pars{n - i}z^{n} \\[5mm]&=z + \sum_{i\ =\ 1}^{\infty}{\rm X}\pars{i} \sum_{n\ =\ 1 + i}^{\infty}{\rm X}\pars{n - i}z^{n} =z + \sum_{i\ =\ 1}^{\infty}{\rm X}\pars{i} \sum_{n\ =\ 1}^{\infty}{\rm X}\pars{n}z^{n + i} \\[5mm]&=z + \bracks{\sum_{i\ =\ 1}^{\infty}{\rm X}\pars{i}z^{i}} \bracks{\sum_{n\ =\ 1}^{\infty}{\rm X}\pars{n}z^{n}}=z + {\cal X}^{2}\pars{z} \end{align}

Then, $\ds{{\cal X}^{2}\pars{z} - {\cal X}\pars{z} + z = 0}$. This $\ds{{\cal X}\pars{z}}$-equation has two solutions: $\ds{1 \pm \root{1 - 4z} \over 2}$. Since $\ds{\lim_{z\ \to\ 0}{\cal X}\pars{z} = 0}$, the $\ds{{\cal X}\pars{z}}$ correct solution is given by: \begin{align} {\cal X}\pars{z}&={1 - \root{1 - 4z} \over 2} =\half\bracks{1 - \sum_{n\ =\ 0}^{\infty}{1/2 \choose n}\pars{-4z}^{n}} =-\,\half\sum_{n\ =\ 1}^{\infty}{1/2 \choose n}\pars{-1}^{n}4^{n}z^{n} \end{align}

which leads to \begin{align}{\rm X}\pars{n}&=-\,\half{1/2 \choose n}\pars{-1}^{n}4^{n} =\pars{-1}^{n + 1}{1/2 \choose n}2^{2n - 1} =\pars{-1}^{n + 1}\,{\Gamma\pars{3/2} \over n!\,\Gamma\pars{3/2 - n}}\,2^{2n - 1} \\[5mm]&=\pars{-1}^{n + 1}\root{\pi}\,{1 \over n!}\, {1 \over \Gamma\pars{3/2 - n}}\,2^{2n - 2}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\pars{1} \end{align}

However, by using well known Gamma Function identities:

\begin{align} \Gamma\pars{{3 \over 2} - n}& ={\pi \over \Gamma\pars{n - 1/2}\sin\pars{\pi\bracks{n - 1/2}}} ={\pi\over \bracks{\Gamma\pars{n + 1/2}/\pars{n - 1/2}}\bracks{-\cos\pars{n\pi}}} \\[5mm]&={\pi\pars{-1}^{n + 1}\pars{n - 1/2} \over \Gamma\pars{n + 1/2}} =\pi\pars{-1}^{n + 1}\pars{n - 1/2}\, {\pars{2\pi}^{-1/2}2^{2n - 1/2}\Gamma\pars{n} \over \Gamma\pars{2n}} \\[5mm]&=\root{\pi}\pars{-1}^{n + 1}2^{2n - 2}\pars{2n - 1} \,{\pars{n - 1}! \over \pars{2n - 1}!} =\root{\pi}\pars{-1}^{n + 1}2^{2n - 2} \,{\pars{n - 1}! \over \pars{2n - 2}!} \\[5mm]&=\root{\pi}\pars{-1}^{n + 1}2^{2n - 2}\,{1 \over \pars{n - 1}!}\, {1 \over {2n - 2 \choose n - 1}} \end{align}

which we'll replace in expression $\pars{1}$: $$\color{#66f}{\large{\rm X}\pars{n}} =\color{#66f}{\large{1 \over n}\,{2n - 2 \choose n - 1}} \quad\imp\quad \color{#66f}{\large{\rm X}\pars{n + 1}} =\color{#66f}{\large{1 \over n + 1}\,{2n \choose n}} $$