# Showing that $\lim_{n \to \infty}\frac{c_n}{4^n} = 0$

Here $$c_n$$ represents the Catalan numbers. This question is from an old exam paper with no solutions available. I have an approach to the problem but it feels very long-winded considering only a few marks are available, so I wanted to see if I was missing a trick.

We have just derived the generating function for the Catalan numbers

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

I proceeded by using the generalised binomial expansion theorem on $$(1-4x)^\frac{1}{2}$$, negating the upper index and eventually arriving at

$$c_n = -{n-\frac{1}{2}\choose n + 1}2^{2n+1}$$

and so

$$\frac{c_n}{4^n} = -2{n-\frac{1}{2}\choose n + 1}=-\frac{2}{(n+1)!}\prod_{k=0}^n\left(n-\frac{1}{2}-k\right)=-2\prod_{k=0}^n\left(\frac{n-\frac{1}{2}-k}{n+1-k}\right)$$

For each $$k$$ the term in the product is less than one and so the product tends to zero (actually I feel like this isn't enough since the terms approach 1 as $$n \to \infty$$ so I could use with some help justifying that too).

Is there a more obvious approach going directly from the generating function or if my approach seems to be appropriate, how can I justify the last step?

• Have you tried using Stirling's approximation for factorials? Or, you could see this: en.wikipedia.org/wiki/…. Commented Apr 18, 2019 at 9:29
• The second link is very helpful. Thank you. Commented Apr 18, 2019 at 10:27

After spending more time thinking about this problem, I've figured out how to prove this directly from the generating function. I will leave this as an answer in case anyone else stumbles across this problem.

By definition, we have

$$C(x)=\sum_{n=0}^\infty c_n x^n$$

Therefore

$$\sum_{n=0}^\infty \frac{c_n}{4^n} = C\left(\frac{1}{4}\right) = \frac{1-\sqrt{1-4\times\frac{1}{4}}}{2\times\frac{1}{4}}=2$$

Since the series converges, the summands must tend to zero which is exactly what we were after.

• From an exam paper where part 1 of the question is a derivation of the GF? Then this is clearly what they expect you to answer. :) Commented Apr 24, 2019 at 12:29