Generating Functions and their Applications

Khizer Shahid and Benjamin Gallai

What is a Generating Function?

The generating function of a sequence \(a_0, a_1, a_2, a_3, \cdots\) is the power series: \[A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3+\cdots + a_kx^k+\cdots\] For example, the generating function for the sequence \(1, 2, 3, 4, 5, \cdots\) is \(A(x) = 1+2x^2+3x^3+4x^4 +\cdots\). Additionally, the generating function for the Fibonacci sequence, \(0, 1, 1, 2, 3, 5, \cdots\), is \(B(x) = 0+x+x^2+2x^3+3x^4+5x^5\cdots\). Note that we are using the polynomial to keep track of information. We will not examine the convergence of a series in this paper; i.e., we may say that \[\begin{aligned} 1+x+x^2+x^3+x^4+x^5+\cdots = \frac{1}{1-x}.\end{aligned}\] The function is only storing information about the polynomial. However, when we compute sums, we must check for convergence. For example, we cannot plug in \(x=2\) into \(1+x+x^2+\cdots = \frac{1}{1-x}\); if we do we get the equation \(1+2+2^2+2^3+\cdots = -1\). Additionally, the reader should note that the left hand side of \((\star)\) is a power series while the right hand side is a rational function.

Finding the Generating Function of a Sequence

We will find the generating function of a sequence below.

Fibonacci Generating Function   Find the generating function for the Fibonacci sequence, \(\{ F_n\}_{n = 0} ^ {\infty} = \{0, 1, 1, 2, 3, 5, \cdots\}\), which is defined recursively as \(F_n = F_{n-1} + F_{n-2}\) for \(n \ge 2\) with \(F_0 = 0\) and \(F_1 = 1\).

Let the generating function for \({F_n}\) be \(F(x)\). By the definition of the generating function, we have

\[\begin{aligned} F(x) &= F_0 + F_1x + F_2x^2 + F_3x^3 + F_4x^4 \cdots \\ &= 0 + x + 1x^2 + 2x^3 + 3x^4+ \cdots\end{aligned}\] Now, we must use the recurrence relationship. First, we will rewrite \(F(x) = \displaystyle\sum_{n\ge0} F_n x^n\). To apply the recurrence relationship, we need \(n \ge 2\). Hence, we can further rewrite this as \(\displaystyle\sum_{n\ge0} F_n x^n = F(x) = F_0 + F_1x + \displaystyle\sum_{n\ge2} F_n x^n\) . Now, we may apply the recurrence relationship. We have \[\begin{aligned} F(x) &= F_0 + F_1x + \sum_{n\ge2} F_n x^n \\ &= 0 + x + \sum_{n\ge2} (F_{n-1} + F_{n-2}) x^n \\ &= x + \sum_{n\ge2} F_{n-1} x^n + \sum_{n\ge2} F_{n-2} x^n \\ &= x + x\sum_{n\ge2} F_{n-1} x^{n-1} + x^2\sum_{n\ge2} F_{n-2} x^{n-2} \end{aligned}\] Now, we have some expressions that look similar to our original expression for \(F(x)\). First, \[\displaystyle\sum_{n\ge2} F_{n-2} x^{n-2} = \displaystyle\sum_{j\ge 0} F_{j} x^{j} = F(x)\] Also, \[\displaystyle\sum_{n\ge2} F_{n-1} x^{n-1} = \displaystyle\sum_{n\ge 1} F_{n} x^{n} = \displaystyle\sum_{n\ge 0} F_{n} x^{n} - F_0 = F(x)\] Hence,

\[\begin{aligned} F(x) &= x + x\sum_{n\ge2} F_{n-1} x^{n-1} + x^2\sum_{n\ge2} F_{n-2} x^{n-2} \\ &= x + x \cdot (F(x) - F_0) + x^2 \cdot F(x) \\ &= x + xF(x) + x^2F(x) \end{aligned}\] We may solve for \(F(x)\). Subtracting \(xF(x) + x^2 F(x)\) from both sides, we have \[\begin{aligned} x &= F(x) - xF(x) - x^2F(x) \\ &= F(x) \left (1 - x - x^2 \right) \\\end{aligned}\]

Dividing by \(1-x-x^2\), we have \(F(x) = \displaystyle\frac{x}{1-x-x^2}\). Again, we took a polynomial and turned it into a rational expression.

Finding the Closed Form of a Recurrence

We have the generating function for the Fibonacci sequence. From this, we may find the closed form for \(F_n\).

Deriving Binet’s Formula  Find the closed form for the \(n^{\text{th}}\) term of the Fibonacci sequence.

We may do this by the partial fraction decomposition of \(F(x)\). In other words, we are trying to find \(A, B \in \mathbb{R}\) such that \[\frac{x}{1-x-x^2} = \frac{A}{\alpha - x} + \displaystyle\frac{B}{\beta - x} \tag{1}\]

where \(\alpha\) and \(\beta\) are roots of \(x^2+x-1\), with \(\alpha > \beta\), meaning that \(1-x-x^2 = - (x^2+x-1) = -(x-\alpha)(x-\beta) = - (\alpha - x)(\beta -x)\). Multiplying both sides of \((1)\) by \((\alpha - x)(\beta -x)\), we have \[\begin{aligned} \frac{x(\alpha - x)(\beta -x)}{1-x-x^2} &= A(\beta -x) + B(\alpha -x) \\ -x &= A(\beta -x) + B(\alpha -x) \end{aligned}\]

Plugging in \(x = \alpha\) into \((2)\), we have \(-\alpha = A(\beta-\alpha) + B(\alpha - \alpha) = A(\beta - \alpha) \Rightarrow A = \frac{\alpha}{\alpha - \beta}\). Similarly, plugging in \(x = \beta\) into \((2)\), we get \(B = \frac{\beta}{\beta - \alpha}\). Now, we can compute \(\alpha - \beta\) using the fact that \((\alpha - \beta)^2 = (\alpha + \beta)^2 - 4\alpha\beta\). By Vieta’s formulas, \(\alpha + \beta = -1\) and \(\alpha\beta = -1\), hence \((\alpha - \beta)^2 = (-1)^2 - 4\cdot (-1) = 5\). We will take \(\alpha - \beta\) as \(\sqrt{5}\). Since \(\alpha - \beta = \sqrt{5} > 0\), \(\alpha\) is the larger of the two roots of \(x^2+x-1\). Therefore, \(A = \frac{\alpha}{\sqrt{5}}\) and \(B = -\frac{\beta}{\sqrt{5}}\). Hence, we may write \(F(x)\) as \(\dfrac{\frac{\alpha}{\sqrt{5}}}{\alpha - x} + \dfrac{-\frac{\beta}{\sqrt{5}}}{\beta - x} = \dfrac{1}{\sqrt{5}} \left ( \dfrac{\alpha}{\alpha - x} - \dfrac{\beta}{\beta - x} \right)\). Now, let’s try to rewrite \(\dfrac{\alpha}{\alpha - x}\) and \(\dfrac{\beta}{\beta - x}\). These look similar to \(\frac{1}{1-x} = 1+x+x^2+x^3+\cdots\). We can manipulate \(\dfrac{\alpha}{\alpha - x}\) to look more like \(\dfrac{1}{1-x}\) by dividing the numerator and denominator by \(\alpha\): \(\dfrac{\alpha}{\alpha - x} = \dfrac{1}{1-\left(\frac{x}{\alpha} \right)}\). If \(\left| \dfrac{x}{\alpha}\right| < 1\), we can rewrite \(\dfrac{1}{1-\left(\frac{x}{\alpha} \right)}\) as the series \(1+ \left (\frac{x}{\alpha} \right) + \left (\frac{x}{\alpha} \right)^2 + \left (\frac{x}{\alpha} \right)^3 + \cdots\). Similarly, if \(\left| \dfrac{x}{\beta}\right| < 1\), we can rewrite \(\frac{\beta}{\beta - x}\) as \(1+ \left (\frac{x}{\beta} \right) + \left (\frac{x}{\beta} \right)^2 + \left (\frac{x}{\beta} \right)^3 + \cdots\). Hence, we can rewrite \(F(x)\):

\[\begin{aligned} F(x) &= \frac{1}{\sqrt{5}} \left (\frac{\alpha}{\alpha - x} - \frac{\beta}{\beta - x} \right) \\ &= \frac{1}{\sqrt{5}} \left ( \left[ 1+ \left (\frac{x}{\alpha} \right) + \left (\frac{x}{\alpha} \right)^2 + \left (\frac{x}{\alpha} \right)^3 + \cdots \right] - \left[ 1+ \left (\frac{x}{\beta} \right) + \left (\frac{x}{\beta} \right)^2 + \left (\frac{x}{\beta} \right)^3 + \cdots \right] \right) \\ &= \frac{1}{\sqrt{5}} \left ( \sum_{n \ge 0} \left (\frac{x}{\alpha} \right)^n - \sum_{n \ge 0} \left (\frac{x}{\beta} \right)^n \right) = \frac{1}{\sqrt{5}} \left ( \sum_{n \ge 0} \left [ \left (\frac{x}{\alpha} \right)^n - \left (\frac{x}{\beta} \right)^n \right] \right) \\ &= \frac{1}{\sqrt{5}} \sum_{n \ge 0} \left [\frac{1}{\alpha^n} - \frac{1}{\beta^n} \right] x^n = \frac{1}{\sqrt{5}} \sum_{n \ge 0} \left [\frac{1}{\left (\tfrac{ -1+\sqrt{5}}{2} \right)^n} - \frac{1}{\left (\tfrac{ -1-\sqrt{5}}{2} \right)^n} \right]x^n \\ &= \frac{1}{\sqrt{5}} \sum_{n \ge 0} \left [\left (\frac{1+\sqrt{5}}{2} \right)^n - \left (\frac{1-\sqrt{5}}{2} \right)^n \right]x^n\end{aligned}\]

Therefore, the coefficient of \(x^n\) in \(F(x)\) is \(\frac{1}{\sqrt{5}} \left [\left (\frac{1+\sqrt{5}}{2} \right)^n - \left (\frac{1-\sqrt{5}}{2} \right)^n \right]\). However, since we defined \(F(x)\) as the generating function of \({F_n}\), the coefficient of \(x^n\) is also \(F_n\). Hence, we have that \(F_n = \frac{1}{\sqrt{5}} \left [\left (\frac{1+\sqrt{5}}{2} \right)^n - \left (\frac{1-\sqrt{5}}{2} \right)^n \right]\). This is known as Binet's formula.

Transforming Generating Functions

Given a generating function, \(A(x)\), for a sequence \(\{A_n\}\), what other generating functions can we find in terms of \(A(x)\)? Well, the generating function for \(\{A_n + k \}\) is \(A(x) + k + kx + kx^2 + \cdots = A(x) + \frac{k}{1-kx}\). Additionally, the generating function for \(\{kA_n\}\) is \(kA(x)\). How can we get the generating function for a sequence like \(\{na_n\}\)? Lets write out \(A(x)\) first:

\[A(x) = A_0 + A_1x + A_2x^2 + A_3x^3 + A_4x^4+\cdots\]

Multiplying each term by its index is the same as multiple the term by the degree of its term. This can be done by differentiation! Taking the derivative of both sides with respect to \(x\), we have

\[\begin{aligned} A'(x) &= 0 \cdot A_0 + 1 \cdot A_1 + 2 \cdot A_2x^1 + 3 \cdot A_3x^2 + 4 \cdot A_4x^3+\cdots \\ &= A_1 + 2A_2x + 3A_3x^2 + 4A_4x^3 +\cdots \\\end{aligned}\] We also need to multiply by \(x\) so that the degree of each term matches the index of the term. Hence, the desired generating function is \(xA'(x)\).

Similarly, let’s find the generating function of \(\left \{\dfrac{A_n}{n+1} \right\}\). If we integrate the general term of our generating function \(A_nx^n\) with respect to \(x\), we get \(\dfrac{1}{n+1} A_n x^{n+1}\). Dividing by \(x\), we have \(\dfrac{A_n}{n+1} x^n\). Hence, the generating function of \(\left \{\dfrac{A_n}{n+1} \right\}\) is \(\dfrac{1}{x} \displaystyle\int A(x) dx\).

Convergence

Now that we know about finding generating functions, what values of \(x\) can we plug into them to yield answers that make sense? For example, if we plug in \(x = 1\) into \(F(x) = \dfrac{x}{1-x-x^2} = \displaystyle\sum_{n \ge 0} F_n x^n\), we get \(\sum_{n \ge 0} F_n = \frac{1}{1-1-1} = -1\), which is obviously not true. In order to find the interval of convergence, we can use the ratio test. By the ratio test, we know that \(F(x) = \displaystyle\sum_{n \ge 0} F_n x^n\) will converge if \(\displaystyle\lim_{n \to \infty} \left | \dfrac{F_{n+1} x^{n+1}}{F_n x^n} \right| < 1\). Simplifying this, we have

\[\begin{aligned} \lim_{n \to \infty} \left | \dfrac{F_{n+1} x^{n+1}}{F_n x^n} \right| = \lim_{n \to \infty} \left | \dfrac{F_{n+1}}{F_n} x \right| = |x| \lim_{n \to \infty} \left | \dfrac{F_{n+1}}{F_n} \right| < 1\end{aligned}\]

Hence, we must have \[|x| < \dfrac{1}{\displaystyle\lim_{n \to \infty} \left | \dfrac{F_{n+1}}{F_n} \right|} = \displaystyle\lim_{n \to \infty} \left | \dfrac{F_n}{F_{n+1}} \right|\]

We just have to compute what \(\displaystyle\lim_{n \to \infty} \left | \dfrac{F_n}{F_{n+1}} \right| = \displaystyle\lim_{n \to \infty} \dfrac{F_n}{F_{n+1}} = L\) is.

We have

\[\begin{aligned} \lim_{n \to \infty} \dfrac{F_n}{F_{n+1}} = \lim_{n \to \infty} \dfrac{F_n}{F_n + F_{n-1}} = \frac{1}{\displaystyle\lim_{n \to \infty} \tfrac{F_n + F_{n-1}}{F_n}} = \frac{1}{\displaystyle\lim_{n \to \infty} \left(1 + \tfrac{F_{n-1}}{F_n} \right)} = \frac{1}{1 + \displaystyle\lim_{n \to \infty} \tfrac{F_{n-1}}{F_n}} = \frac{1}{1 + \displaystyle\lim_{n \to \infty} \tfrac{F_{n}}{F_{n+1}}} \end{aligned}\]

Therefore, \(L = \frac{1}{1+L} \Rightarrow L^2 + L - 1 =0\). Hence, \(L\) is either \(\frac{-1+\sqrt{5}}{2}\) or \(\frac{-1-\sqrt{5}}{2}\). However, \(L > 0\) and \(\frac{-1-\sqrt{5}}{2} <0\), so \(L = \frac{-1+\sqrt{5}}{2}\). Plugging this into our inequality, we have that \(F(x)\) will converge if \(|x| <\frac{\sqrt{5}-1}{2}\). Since \(1 > \frac{\sqrt{5}-1}{2}\), it is expected that we get a nonsensical answer.

Computing Sums

Now that we understand when generating functions converge, we can finally compute sums!

Fibonacci Sum  Compute \[\sum_{n = 0} ^{\infty} \frac{F_n}{2^n}.\]

We will present two solutions – one using manipulations and other using generating functions.

Solution 1 Let \(S\) be the desired sum.

We have \[\begin{aligned} S &= \frac{F_0}{2^0} + \frac{F_1}{2^1} + \frac{F_2}{2^2} + \frac{F_3}{2^3} +\cdots \\ \frac{S}{2} &= ~~~~~~~~ \frac{F_0}{2^1} + \frac{F_1}{2^2} + \frac{F_2}{2^3} + \cdots\end{aligned}\]

Subtracting the two equations, we have

\[\begin{aligned} S - \frac{S}{2} &= \frac{F_0}{2^0} + \frac{F_1 - F_0}{2^1} + \frac{F_2 - F_1}{2^2} + \frac{F_3 - F_2}{2^3} +\cdots \\ \frac{S}{2}&= \frac{0}{1} + \frac{1}{2} + \frac{F_0}{2^2} + \frac{F_1}{2^3} +\cdots \\ &= \frac{1}{2} + \frac{S}{4}\end{aligned}\]

Solving for \(S\), we have that \(S = 2\).

Solution 2 Rewrite the given sum as \(\displaystyle\sum_{n = 0} ^{\infty} F_n \cdot \left(\frac{1}{2}\right)^n = F \left(\dfrac{1}{2} \right)\). Additionally, since \(\left|\frac{1}{2} \right| < \left | \frac{\sqrt{5}-1}{2} \right|\), \(\frac{1}{2}\) lies inside the interval of convergence of \(F(x)\). Hence, the requested sum is \(\dfrac{\frac{1}{2}}{1 - \frac{1}{2} - \left(\frac{1}{2}\right)^2} = 2\).

Notice that in our generating function solution, we did not take the convergence of our series for granted, as in solution 1.

 Compute \[\sum_{n = 0} ^{\infty} \frac{1}{(n+1) \cdot 2^n}.\]

Let’s start of by replacing \(\dfrac{1}{2}\) with \(x\); our new sum is \(\displaystyle\sum_{n = 0} ^{\infty} \dfrac{x^n}{n+1}\). The generating function for the sequence \(\{1\}\) is \(1+x+x^2+x^3\cdots = \dfrac{1}{1-x}\). So we have \[1 + x + x^2 +x^3 +\cdots = \frac{1}{1-x}\]

Taking the integral of both sides with respect to \(x\), we have \[x + \tfrac{1}{2} x^2 + \tfrac{1}{3} x^3 + \tfrac{1}{4} x^4 + \cdots = -\ln|x-1|\]

Dividing both sides by \(x\), we have \[1 + \tfrac{1}{2} x + \tfrac{1}{3} x^2 + \tfrac{1}{4} x^3 + \cdots = -\tfrac{1}{x}\ln|x-1|\]

Using the ratio test on this series, we find that it converges for \(|x| < 1\). Plugging in \(\frac{1}{2}\), we have that the desired sum is \(2\ln2\).

 Compute \[\sum_{n = 0} ^{\infty} \frac{F_n}{n!}.\]

For this problem, we cannot use the generating function we already found for \(\{F_n\}\). We must instead derive a generating function for \(\{\frac{F_n}{n!}\}\). We will call this sequence \(\{A_n\}\). We see that \(A_0=\frac{0}{0!}\), \(A_1=\frac{1}{1!}\), and \[A_n = \frac{A_{n-1}(n-1)!+A_{n-2}(n-2)!}{n!}.\] Removing fractions, we simplify to \[n(n-1)A_n = (n-1)A_{n-1}+A_{n-2}. \tag{$\ast$}\]

We can now write out the generating function \(A(x)=A_0+A_1x+A_2x^2+A_3x^3+\cdots\). Part of the motivation to have written \((\ast)\) the way we did (as opposed to isolating \(A_n\)), is that twice differentiating \(A(x)\) will give us a very similar form

\[\begin{aligned} A(x) &= A_0+A_1x+A_2x^2+A_3x^3+\cdots \\ A'(x) &= 1A_1 + 2A_2x + 3A_3x^2+4A_4x^3+\cdots \\ A''(x) &= 2\cdot1A_2+3\cdot2A_3x+4\cdot3A_4x^2+5\cdot4A_5x^3+\cdots \\ &= (A_1+A_0) + (2A_2+A_1)x + (3A_3+A_2)x^2 + (4A_4+A_3)x^3 + \cdots \\ &= (A_1+2A_2x+3A_3x^2+\cdots) + (A_0+A_1x+A_2x^2) + \cdots \\ &= A'(x) + A(x)\end{aligned}\]

To solve this differential equation, we know that \(A(x)\) must be of the form \(e^{ax}\) or \(\sum e^{ix}\).

\[\begin{aligned} a^2e^{ax} &= ae^{ax} + e^{ax} \\ a^2-a-1 &= 0 \\ a &= \frac{1\pm\sqrt{5}}{2}\end{aligned}\]

Thus, \(A(x)=pe^{\frac{1+\sqrt{5}}{2}x}+qe^{\frac{1-\sqrt{5}}{2}x}\). To solve for \(p\) and \(q\), we use the fact that \(A(0)=A_0=0 \Rightarrow A(0)=p+q=0 \Rightarrow p=-q\). We also know that \(A'(0) = A_1 = 1\)

\[\begin{aligned} A'(x)&=p\frac{1+\sqrt{5}}{2}e^{\frac{1+\sqrt{5}}{2}}-p\frac{1-\sqrt{5}}{2}e^{\frac{1-\sqrt{5}}{2}} \\ A'(0)&=p \left(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2} \right) =1\\ \Rightarrow p&=\frac{1}{\sqrt{5}}\end{aligned}\]

Finally, we know that \(A(x)=\frac{e^{\frac{1+\sqrt{5}}{2}x}-e^{\frac{1-\sqrt{5}}{2}x}}{\sqrt{5}}\). Our desired sum is simply \(A(1) \approx \fbox{2.0143}\).

A Final Example

Catalan Numbers  Find the generating function for the Catalan numbers, which are defined by the recursion \(C_{n+1} = \displaystyle\sum_{i=0}^n C_iC_{n-i}\) with \(C_0 = 1\).

Let \(C(x)= C_0 + C_1x+C_2x^2+C_3x^3+\cdots = 1 + x + 2x^2 + 5x^3 +\cdots\) be the desired generating function. Seeing the product of two Catalan numbers, we are motivated to multiply \(C(x)\) by itself. We will find \(C(x)^2\) by finding the coefficient of each term.

For the constant term, we must multiply the two constant terms together. Therefore, \(C(x)^2 = C_0 ^2 +\cdots\)

For the \(x\) term, we can multiply the \(C_0\) from the first \(C(x)\) with the \(C_1\) from the second \(C(x)\) or multiply the \(C_0\) from the first \(C(x)\) with the \(C_1\) from the second \(C(x)\). Therefore, the coefficient of \(x\) is \(C_0C_1 + C_1C_0\). However, this is just \(C_2\). So we can write \(C(x)^2 = C_0^2 + C_2x + \cdots\).

In general, the \(x^{k}\) term will be \(C_0C_k + C_1C_{k-1} + \cdots +C_kC_0 = C_{k+1}\). Therefore, \(C(x)^2 = C_0^2 + C_2x + C_3x^2 + \cdots + C_{k+1}x^k +\cdots\). Also, \(C_0 ^2 = 1 = C_1\), so we can write \(C(x)^2 = C_1 + C_2x + C_3x^2 + \cdots\). This is similar to \(C(x) = C_0+C_1x+ C_2 x^2 +\cdots\). We can connect the two: \(xC(x)^2 + C_0 = C(x) \Rightarrow xC(x)^2 - C(x) + 1 = 0\), which is a quadratic in \(C(x)\). Solving for \(C(x)\), we have \(C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}\). In order to decide which one to choose, we will expand \(\sqrt{1-4x}\). To do this, we must use the generalized binomial theorem, which states that for any real \(r\)

\[(1+x)^r = \sum_{n \ge 0} \binom{r}{n} x^n ~~\text{where}~~ \binom{r}{n} = \frac{r(r-1)(r-2)\cdots ( r-n+1)}{n!}\] Using this, we have \[\sqrt{1-4x} = \sum_{n = 0} ^{\infty} \binom{\tfrac{1}{2}}{n} (-4x)^n = \sum_{n=0} ^{\infty} \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})\cdots(\frac{3-2n}{2})}{n!}(-4x)^n\] Note that this is negative for all values of n, so we can take out a negative sign from the summation, and rewrite it as \[-\sum_{n=0} ^{\infty} 2^n \frac{(2n-3)!!}{n!} x^n.\] Here, the double exclamation marks represent the double factorial function, which only multiplies integers of same parity; for example, \(10!! = 10\cdot 8 \cdot 6 \cdot 4 \cdot 2\), while \(7!! = 7 \cdot 5 \cdot 3 \cdot 1\). Since the terms of our power series are positive, we must take the negative square root. Hence, \(C(x) = \frac{1 -\sqrt{1-4x}}{2x}\). We can even find the general term of our sequence. Substituting the power series expansion of \(\sqrt{1-4x}\) into our generating function, we have \[C(x) = \frac{1 + \displaystyle\sum_{n=0} ^{\infty} 2^n \frac{(2n-3)!!}{n!} x^n}{2x}.\] The coefficient of \(x^n\) is \[\frac{2^{n+1} \tfrac{(2n-1)!!}{(n+1)!}}{2} = 2^{n} \cdot\frac{(2n-1)!!}{(n+1)!} = 2^{n} \cdot\frac{(2n-1)!!}{(n+1)!} \cdot \frac{(2n)!!}{(2n)!!} = 2^n \frac{(2n)!}{(2n)!!(n+1)!} = \frac{(2n)!}{n!(n+1)!} = \frac{\binom{2n}{n}}{n+1}.\] Therefore, we have \(C_n = \displaystyle\frac{1}{n+1}\binom{2n}{n}\).