7
$\begingroup$

I'm trying to follow a proof of the Catalan numbers being equal to $\frac{1}{n+1} {2n \choose n}$ from the recurrence relation $C_n = C_0C_{n-1}+C_1C_{n-2}+...+C_{n-2}C_{1}+C_{n-1}C_0$

Now it's seen that the generating function satisfies $xf^2-f+1=0$ so $f=\frac{1-\sqrt{1-4x}}{2x}$ since the other root has a pole at 0 but I'm struggling to see how $f=\frac{1-\sqrt{1-4x}}{2x}$ can be expanded to obtain the necessary power series

I've seen Wikipedia's proof but I don't see how ${ \frac{1}{2} \choose n} = \frac{(-1)^{n+1}}{4^n(2n-1)} {2n \choose n}$ nor how this gets lost into ${2n \choose n}$ via plugging y=-4x and putting it into the expression $f=\frac{1-\sqrt{1-4x}}{2x}$

$\endgroup$
  • $\begingroup$ Binomial series might be of some help $\endgroup$ – Wojowu Apr 21 '16 at 15:20
  • $\begingroup$ also Maclaurin Series can help $\endgroup$ – Leox Apr 21 '16 at 15:22
  • $\begingroup$ See en.wikipedia.org/wiki/Catalan_number#Proof_of_the_formula $\endgroup$ – lab bhattacharjee Apr 21 '16 at 15:25
  • $\begingroup$ Yes I have also looked at this but I don't see how ${ \frac{1}{2} \choose n} = \frac{(-1)^{n+1}}{4^n(2n-1)} {2n \choose n}$ nor how this gets lost into ${2n \choose n}$ via plugging it in $\endgroup$ – user142702 Apr 21 '16 at 15:28
6
$\begingroup$

Hint: By binomial theorem, we have $$(1 + z)^\alpha = \sum\limits_{k \geq 0} \binom{\alpha}{k} z^k.$$

Use this for $\alpha = \frac{1}{2}$ on the square root term, and equate coefficients.


Edit: Here, we define $$\binom{\alpha}{k} = \frac{\alpha(\alpha - 1)\cdots(\alpha - (k-1))}{k!}.$$

Note that this agrees with our usual definition when $\alpha$ is an integer.


Edit 2: We have \begin{align} \frac{1 + \sum_{n \geq 0} \binom{2n}{n} \frac{x^n}{2n - 1}}{2x} &= \frac{1 + (-1) + \sum_{n \geq 1} \binom{2n}{n} \frac{x^n}{2n - 1}}{2x} \\ &= \sum\limits_{n \geq 1}\binom{2n}{n} \frac{x^{n-1}}{(2n-1)2} \\ &= \sum\limits_{n \geq 0} \binom{2n+2}{n+1} \frac{x^n}{2(2n + 1)} \\ &= \sum\limits_{n \geq 0} \frac{(2n + 2)!}{(n+1)!(n+1)!} \frac{x^n}{2(2n + 1)} \\ &=\sum\limits_{n \geq 0} \frac{(2n + 2)(2n+1)(2n)!}{(n+1)(n+1)(n!)(n!)} \frac{x^n}{2(2n + 1)}\\ &= \sum\limits_{n \geq 0} \binom{2n}{n}\frac{x^n}{n + 1} \end{align}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But how does one expand a fractional binomial coefficient? $\endgroup$ – user142702 Apr 21 '16 at 15:35
  • $\begingroup$ @user142702, Ah, I added a bit to explain that. $\endgroup$ – Marcus M Apr 21 '16 at 15:36
  • $\begingroup$ Thank you! I get that $\sqrt{1-4x} = \displaystyle\Sigma_0^\infty \frac{(-1)}{2n-1} {2n \choose n} x^n$ $\endgroup$ – user142702 Apr 21 '16 at 15:51
  • $\begingroup$ So I suppose I'm wondering how to simplify $\frac{1+\Sigma {2n \choose n} \frac{x^n}{2n-1}}{2x}$ $\endgroup$ – user142702 Apr 21 '16 at 15:57
  • $\begingroup$ I think I've got it sorted out, I just noticed that 1/2x is the first term, thank you for the help :) $\endgroup$ – user142702 Apr 21 '16 at 16:06
3
$\begingroup$

Here as supplement to the answer of @MarcusM we show the validity of the binomial identity \begin{align*} \binom{\frac{1}{2}}{n}=\frac{(-1)^{n+1}}{4^n(2n-1)} \binom{2n}{n} \end{align*}

In the following we use as definition of the binomial coefficient \begin{align*} \binom{\alpha}{n}=\frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-n+1)}{n!} \end{align*}

We obtain \begin{align*} \binom{\frac{1}{2}}{n} &=\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\left(\frac{1}{2}-2\right)\cdots\left(\frac{1}{2}-n+1\right)}{n!}\\ &=\frac{1(-1)(-3)\cdots(3-2n)}{2^nn!}\tag{1}\\ &=\frac{(-1)^{n-1}}{2^nn!}(2n-3)!!\tag{2}\\ &=\frac{(-1)^{n-1}}{2^nn!(2n-1)}(2n-1)!!\tag{3}\\ &=\frac{(-1)^{n-1}}{2^nn!(2n-1)}\cdot\frac{(2n)!}{(2n)!!}\tag{4}\\ &=\frac{(-1)^{n-1}}{2^nn!(2n-1)}\cdot\frac{(2n)!}{2^nn!}\tag{5}\\ &=\frac{(-1)^{n+1}}{4^n(2n-1)}\cdot\frac{(2n)!}{n!n!}\tag{6}\\ &=\frac{(-1)^{n+1}}{4^n(2n-1)}\binom{2n}{n} \end{align*} and the claim follows.

Comment:

  • In (1) we factor out $2^n$

  • In (2) we factor out $(-1)^n$ use as convenient notation double factorial \begin{align*} (2n)!!&=(2n)(2n-2)(2n-4)\cdots 4\cdot 2\\ (2n-1)!!&=(2n-1)(2n-3)(2n-5)\cdots 3\cdot 1\\ \end{align*}

  • In (3) we multiply the expression with $\frac{2n-1}{2n-1}$ and use $(2n-3)!!(2n-1)=(2n-1)!!$

  • In (4) we use the identity \begin{align*} (2n)!=(2n)!!(2n-1)!! \end{align*}

  • In (5) we use the identity \begin{align*} (2n)!!=(2n)(2n-2)\cdots4\cdot2=2^n n! \end{align*}

  • In (6) we do a small rearrangement

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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