Question

Let$\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}$be the sequence of Catalan numbers, that is, the solution to the recurrence relationwith.

(a)Show that ifis the generating function for the sequence of Catalan numbers, then$\mathit{x}\mathit{G}\mathbf{(}\mathbf{x}{\mathbf{)}}^{\mathbf{2}}\mathbf{-}\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{+}\mathbf{1}\mathbf{=}\mathbf{0}$. Conclude (using the initial conditions) that$\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}\mathbf{(}\mathbf{1}\mathbf{-}\sqrt{\mathbf{1}\mathbf{-}\mathbf{4}\mathbf{x}}\mathbf{)}\mathbf{/}\mathbf{\left(}\mathbf{2}\mathit{x}\mathbf{\right)}$.

(b) Use Exercise 40 to conclude that $\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}\mathbf{\sum }_{\mathbf{n}\mathbf{=}\mathbf{0}}^{\mathbf{\infty }}\frac{\mathbf{1}}{\mathbf{n}\mathbf{+}\mathbf{1}}\left(\begin{array}{c}2n\\ n\end{array}\right){\mathit{x}}^{\mathbf{n}}\mathbf{,}$so that${\mathit{C}}_{\mathbf{n}}\mathbf{=}\frac{\mathbf{1}}{\mathbf{n}\mathbf{+}\mathbf{1}}\left(\begin{array}{c}2n\\ n\end{array}\right)\mathbf{.}$

(c) Show that${\mathit{C}}_{\mathbf{n}}\mathbf{⩾}{\mathbf{2}}^{\mathbf{n}\mathbf{-}\mathbf{1}}$for all positive integers$\mathit{n}$.

Short answer

(a)The resultant answer is$G\left(x\right)=\frac{-(-1)\pm \sqrt{{(-1)}^2-4\left(x\right)\left(1\right)}}{2x}=\frac{1\pm \sqrt{1-4x}}{2x}$.

(b)The resultant answer is localid="1668677496153" $C_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)$

(c) The resultant answer is $C_n⩾2^{n-1}$.

Step-by-step solution

Given data

The given data is:

$C_n=\sum _{k=0}^{n-1}{C}_k{C}_{n-k-1}$

$C_0=C_1=1$

Concept of Extended binomial theorem

Generating function for the sequence ${\mathit{a}}_{\mathbf{0}}\mathbf{,}{\mathit{a}}_{\mathbf{1}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{k}}\mathbf{,}\mathbf{\dots }$of real numbers is the infiniteseries:

$\mathit{G}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}{\mathit{a}}_{\mathbf{0}}\mathbf{+}{\mathit{a}}_{\mathbf{1}}\mathit{x}\mathbf{+}{\mathit{a}}_{\mathbf{2}}{\mathit{x}}^{\mathbf{2}}\mathbf{+}\mathbf{\dots }\mathbf{+}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}\mathbf{+}\mathbf{\dots }\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}{\mathit{a}}_{\mathbf{k}}{\mathit{x}}^{\mathbf{k}}$

Extended binomial theorem:

$\mathit{x}{\mathbf{(}\mathbf{1}\mathbf{+}\mathbf{x}\mathbf{)}}^{\mathbf{u}}\mathbf{=}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{+}\mathbf{\infty }}\left(\begin{array}{c}u\\ k\end{array}\right){\mathit{x}}^{\mathbf{k}}$

Simplify the expression

(a)

Let $G\left(x\right)=\sum _n^{+}{c}_X{x}^n$

$xG(x{)}^2-G\left(x\right)+1=x\sum _{n=0}^{+\infty }\sum _{k=0}^n{C}_k{C}_{n-k}{x}^n-\sum _{n=0}^{+\infty }{C}_n{x}^n+1$

$xG(x{)}^2-G\left(x\right)+1=\sum _{n=0}^{+\infty }\sum _{k=0}^n{C}_k{C}_{n-k}{x}^{n+1}-\sum _{n=1}^{+\infty }{C}_n{x}^n+1-C_0$

Similarly;

$xG(x{)}^2-G\left(x\right)+1=\sum _{n=0}^{+\infty }\sum _{k=0}^n{C}_k{C}_{n-k}{x}^{n+1}-\sum _{n=1}^{+\infty }{C}_n{x}^n+1-1$

$xG(x{)}^2-G\left(x\right)+1=\sum _{n=1}^{+\infty }\sum _{k=0}^{n-1}{C}_k{C}_{n-k-1}{x}^n-\sum _{n=1}^{+\infty }\sum _{k=0}^{n-1}{C}_k{C}_{n-k-1}{x}^n{C}_n=\sum _{k=0}^{n-1}{C}_k{C}_{n-k-1}$

$xG(x{)}^2-G\left(x\right)+1=0$

Similarly;

We have then obtained $xG(x{)}^2-G\left(x\right)+1=0$

Determine the roots using the quadratic formula:

$G\left(x\right)=\frac{-(-1)\pm \sqrt{{(-1)}^2-4\left(x\right)\left(1\right)}}{2x}=\frac{1\pm \sqrt{1-4x}}{2x}$

If you choose the positive sign, then the first term of the series will be $\frac{1}{x}$determined using technology) and thus the terms does not exist when$x=0$.

We then need to choose the negative sign

Simplify by using the concept of Binomial theorem

(b)

Use the extended binomial theorem:

${(1-4x)}^{-1/2}={(1+(-4x\left)\right)}^{-1/2}$

localid="1668673798980" ${(1-4x)}^{-1/2}=\sum _{k=0}^{+\infty }\left(\begin{array}{c}-1/2\\ k\end{array}\right){(-4x)}^k$

localid="1668673834816" ${(1-4x)}^{-1/2}=\sum _{k=0}^{+\infty }\frac{\left(\begin{array}{c}2k\\ k\end{array}\right)}{{(-4)}^k}{(-4)}^k{x}^k$

localid="1668673866139" ${(1-4x)}^{-1/2}=\sum _{k=0}^{+\infty }\left(\begin{array}{c}2k\\ k\end{array}\right)x^k$

Note that $(1-4x{)}^{-1/2}$is the derivative of $G\left(x\right)=\frac{1\pm \sqrt{1-4x}}{2}$thus$xG\left(x\right)$is the integral of

$(1-4x{)}^{-1/2}$

$xG\left(x\right)={\int }_0^x{(1-4x)}^{-1/2}dx$

localid="1668673903804" $xG\left(x\right)={\int }_0^x\sum _{k=0}^{+\infty }\left(\begin{array}{c}2k\\ k\end{array}\right)x^{k}dx$

localid="1668673963573" $xG\left(x\right)=\sum _{k=0}^{+\infty }\left(\begin{array}{c}2k\\ k\end{array}\right){\int }_0^x{x}^{k}dx$

Similarly;

localid="1668673979970" $xG\left(x\right)=\sum _{k=0}^{+\infty }\left(\begin{array}{c}2k\\ k\end{array}\right)\frac{x^{k+1}}{k+1}$

localid="1668673999736" $xG\left(x\right)=\sum _{k=0}^{+\infty }\frac{1}{k+1}\left(\begin{array}{c}2k\\ k\end{array}\right)x^{k+1}$

localid="1668674014569" $xG\left(x\right)=x\sum _{k=0}^{+\infty }\frac{1}{k+1}\left(\begin{array}{c}2k\\ k\end{array}\right)x^k$

We then note that the coefficient of localid="1668676315488" $x^n$is$C_n=\frac{1}{n+1}\left(\begin{array}{c}2n\\ n\end{array}\right)$

Use the strong induction concept and simplify the expression

(c)

Let us assume that $P\left(1\right),P\left(2\right),\dots ,P\left(n\right)$is true and $n⩾1$

$C_k⩾2^{k-1}\text{when}1⩽k⩽n$

We need to prove that $P(n+1)$is true;

$C_{n+1}=\sum _{k=0}^n{C}_k{C}_{n-k-1}$

$C_{n+1}⩾\sum _{k=0}^n{2}^k{2}^{n-k-1}\text{Since}P\left(1\right),P\left(2\right),\dots ,P\left(n\right)\text{is true}$

$C_{n+1}=\sum _{k=0}^n{2}^{n-1}$

$C_{n+1}=(n+1)2^{n-1}$

$C_{n+1}⩾2·2^{n-1}$

$C_{n+1}=2^n$

Thus$P(n+1)$is true.

Conclusion By the principle of strong induction,$P\left(n\right)$is true for all positive integers$n$