Simplifying coefficients in differential equations for generating function of Catalan numbers

Abstract

In the paper, by the Faà di Bruno formula, several identities for the Bell polynomials of the second kind, and an inversion theorem, the authors simplify coefficients in two families of nonlinear ordinary differential equations for the generating function of the Catalan numbers.

Keywords:

• Simplifying
• coefficient
• nonlinear ordinary differential equation
• generating function
• Catalan number
• Faà di Bruno formula
• Bell polynomial of the second kind
• inversion theorem

2010 Mathematics Subject Classification.:

• Primary: 05A15
• Secondary: 11B65
• 11B75
• 11B83
• 15A09
• 15B36
• 34A05
• 34A34
• 40E99

1. Motivation

The Catalan numbers $C_n$ for $n\ge 0$ form a combinatorial sequence of natural numbers that occur in enumeration problems [1, 2]. The Catalan numbers $C_n$ can be explicitly expressed by $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0em}{}{2n}{n}\right)$ and can be formally generated by (1) $\begin{array}{rl}G\left(x\right)& =\frac{2}{1+\sqrt{1-4x}}=\sum _{n=0}^{\mathrm{\infty }}{C}_n{x}^n\\ & =1+x+2x^2+5x^3+14x^4+42x^5+\cdots .\end{array}$(1) In [3, Theorem 2.1], Kim and Kim established recursively and inductively that the family of differential equations (2) $G^{\left(n\right)}\left(x\right)=\sum _{i=1}^n{a}_i\left(n\right)(1-4x{)}^{-(2n-i)/2}{G}^{i+1}(x),n\in \mathbb{N}$(2)

has a solution $G\left(x\right)=2/(1+\sqrt{1-4x})$, where $a_1\left(n\right)=2^{n-1}(2n-3)!!$ and (3) $\begin{array}{rl}{a}_i\left(n\right)& =2^{n-i}i!\sum _{k_{i-1}=0}^{n-i}\sum _{k_{i-2}=0}^{n-i-k_{i-1}}\cdots \sum _{k_1=0}^{n-i-k_{i-1}-\cdots -k_2}\\ & \times \left(2n-2\sum _{j=1}^{i-1}{k}_j-2i-1\right)!!\\ & \times \prod _{\ell =1}^{i-1}{⟨2n-2\sum _{j=\ell +1}^{i-1}{k}_j-2i-1+\ell ;2⟩}_{k_{\ell }}\end{array}$(3) with $⟨x;\alpha {⟩}_0=1$ and $⟨x;\alpha {⟩}_n=x(x-\alpha )\cdots [x-(n-1\left)\alpha \right]$ for $n\in \mathbb{N}$.

In [3, Theorem 3.1], by similar argument as in the proof of [3, Theorem 2.1], they found that the family of differential equations (4) $n!G^{n+1}\left(x\right)=\sum _{i=0}^{\lfloor n/2\rfloor }{b}_i\left(n\right)(1-4x{)}^{n/2-i}{G}^{(n-i)}(x),n\in \mathbb{N}$(4)

has a solution $G\left(x\right)=2/(1+\sqrt{1-4x})$, where $\lfloor t\rfloor$ denotes the floor function whose value is the largest integer less than or equal to t, the coefficients $b_0\left(n\right)=1$ and (5) $b_i\left(n\right)=(-2{)}^i{S}_{n+1-2i,i},1\le i\le ⌊\frac{n}{2}⌋$(5) with $S_{n,1}=n+(n-1)+\cdots +1$ and $S_{n,j}=n{S}_{n+1,j-1}+(n-1)S_{n,j-1}+\cdots +1S_{2,j-1},j\ge 2.$ In [3, Theorems 2.2 and 3.2, [3, Remark]], Kim and Kim also used the coefficients $a_i\left(n\right)$ and $b_i\left(n\right)$ respectively defined in (3(3) $\begin{array}{rl}{a}_i\left(n\right)& =2^{n-i}i!\sum _{k_{i-1}=0}^{n-i}\sum _{k_{i-2}=0}^{n-i-k_{i-1}}\cdots \sum _{k_1=0}^{n-i-k_{i-1}-\cdots -k_2}\\ & \times \left(2n-2\sum _{j=1}^{i-1}{k}_j-2i-1\right)!!\\ & \times \prod _{\ell =1}^{i-1}{⟨2n-2\sum _{j=\ell +1}^{i-1}{k}_j-2i-1+\ell ;2⟩}_{k_{\ell }}\end{array}$(3) ) and (5(5) $b_i\left(n\right)=(-2{)}^i{S}_{n+1-2i,i},1\le i\le ⌊\frac{n}{2}⌋$(5) ) to express their other results in [3]. In other words, the quantities $a_i\left(n\right)$ and $b_i\left(n\right)$ are the core of the paper [3].

It is obvious that the coefficients $a_i\left(n\right)$ and $b_i\left(n\right)$ respectively defined in (3(3) $\begin{array}{rl}{a}_i\left(n\right)& =2^{n-i}i!\sum _{k_{i-1}=0}^{n-i}\sum _{k_{i-2}=0}^{n-i-k_{i-1}}\cdots \sum _{k_1=0}^{n-i-k_{i-1}-\cdots -k_2}\\ & \times \left(2n-2\sum _{j=1}^{i-1}{k}_j-2i-1\right)!!\\ & \times \prod _{\ell =1}^{i-1}{⟨2n-2\sum _{j=\ell +1}^{i-1}{k}_j-2i-1+\ell ;2⟩}_{k_{\ell }}\end{array}$(3) ) and (5(5) $b_i\left(n\right)=(-2{)}^i{S}_{n+1-2i,i},1\le i\le ⌊\frac{n}{2}⌋$(5) ) can not be easily remembered, possibly understood, and simply computed.

The aim of this paper is the same one as in the papers [4–18] and closely related references therein. Concretely speaking, our aim in this paper is to discover simple, significant, meaningful, easily remembered, possibly understood, readily computed expressions for the coefficients $a_i\left(n\right)$ and $b_i\left(n\right)$ in the families (2(2) $G^{\left(n\right)}\left(x\right)=\sum _{i=1}^n{a}_i\left(n\right)(1-4x{)}^{-(2n-i)/2}{G}^{i+1}(x),n\in \mathbb{N}$(2) ) and (4(4) $n!G^{n+1}\left(x\right)=\sum _{i=0}^{\lfloor n/2\rfloor }{b}_i\left(n\right)(1-4x{)}^{n/2-i}{G}^{(n-i)}(x),n\in \mathbb{N}$(4) ) respectively.

2. Lemmas

To reach our aim in this paper, we recall the following lemmas.

Lemma 2.1

[19, p. 134 and 139]

The Faà di Bruno formula can be described in terms of the Bell polynomials of the second kind ${\mathrm{B}}_{n,k}(x_1,x_2,\dots ,x_{n-k+1})$ by (6) $\begin{array}{rl}\frac{{\mathrm{d}}^n}{\mathrm{d}{t}^n}f\circ h\left(t\right)& =\sum _{k=0}^n{f}^{\left(k\right)}\left(h\right(t\left)\right){\mathrm{B}}_{n,k}\\ & \times \left(h^{\prime }\left(t\right),h^{″}\left(t\right),\dots ,h^{(n-k+1)}\left(t\right)\right)\end{array}$(6) for $n\ge 0,$ where the Bell polynomials of the second kind, or say, partial Bell polynomials, denoted by ${\mathrm{B}}_{n,k}(x_1,x_2,\dots ,x_{n-k+1})$ for $n\ge k\ge 0,$ are defined by $\begin{array}{rl}& {\mathrm{B}}_{n,k}(x_1,x_2,\dots ,x_{n-k+1})\\ & =\sum _{\begin{array}{c}1\le i\le n-k+1\\ {\ell }_i\in \left\{0\right\}\cup \mathbb{N}\\ \sum _{i=1}^{n-k+1}i{\ell }_i=n\\ \sum _{i=1}^{n-k+1}{\ell }_i=k\end{array}}\frac{n!}{\prod _{i=1}^{n-k+1}{\ell }_i!}\prod _{i=1}^{n-k+1}{\left(\frac{x_i}{i!}\right)}^{{\ell }_i}.\end{array}$

Lemma 2.2

[19, p. 135]

For $n\ge k\ge 0,$ we have (7) $\begin{array}{rl}& {\mathrm{B}}_{n,k}\left(ab{x}_1,a{b}^2{x}_2,\dots ,a{b}^{n-k+1}{x}_{n-k+1}\right)\\ & =a^k{b}^n{\mathrm{B}}_{n,k}(x_1,x_2,\dots ,x_{n-k+1}),\end{array}$(7) where a and b are any complex numbers.

Lemma 2.3

[20, Theorem 5.17, [21], Theorem 1.2]

For $n\ge k\ge 0,$ we have (8) $\begin{array}{rl}& {\mathrm{B}}_{n,k}\left(\right(-1)!!,1!!,3!!,\dots ,[2(n-k)-1]!!)\\ & =\left[2\right(n-k)-1]!!\left(\genfrac{}{}{0em}{}{2n-k-1}{2(n-k)}\right),\end{array}$(8) where the double factorial of negative odd integers $-(2n+1)$ is defined by $(-2n-1)!!=\frac{(-1{)}^n}{(2n-1)!!}=(-1{)}^n\frac{2^{n}n!}{\left(2n\right)!},n=0,1,\dots .$

Lemma 2.4

[17, Theorem 4.3 and Remark 6.2]

For $n\ge k\ge 1,$ let $\{s_k{\}}_{k\in \mathbb{N}}$ and $\{S_k{\}}_{k\in \mathbb{N}}$ be two sequences which are independent of n. Then $s_n=\sum _{k=1}^n\left(\genfrac{}{}{0em}{}{k}{n-k}\right)S_k$ if and only if $(-1{)}^{n}n{S}_n=\sum _{k=1}^n\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)(-1{)}^{k}k{s}_k.$

Remark 2.1

Every inversion theorem in combinatorics corresponds to a lower triangular invertible matrix and its inverse. Conversely, every lower triangular invertible matrix and its inverse correspond to an inversion theorem. Generally, it is not easy to compute the inverse of a lower triangular invertible matrix.

Lemma 2.4 is equivalent to that the lower triangular integer matrices $A_n=(a_{i,j}{)}_{1\le i,j\le n}$ and $B_n=(b_{i,j}{)}_{1\le i,j\le n}$ with $a_{i,j}=\left\{\begin{array}{ll}0,& i<j\\ \left(\genfrac{}{}{0em}{}{j}{i-j}\right),& j\le i\le 2j\\ 0,& i>2j\end{array}\right.$ and $b_{i,j}=\left\{\begin{array}{ll}0,& 1\le i<j\\ (-1{)}^{i-j}\frac{j}{i}\left(\genfrac{}{}{0em}{}{2i-j-1}{i-1}\right),& i\ge j\ge 1\end{array}\right.$ are inversive to each other. See [17, Theorem 4.1].

Lemma 2.4 has been cited and applied in the papers [4, 15, 22] and closely related references therein.

3. Main results and their proofs

Now we are in a position to state our main results and to prove them simply.

Theorem 3.1

For $n\in \mathbb{N},$ the nth derivative and the powers of the generating function $G\left(x\right)$ defined in (1(1) $\begin{array}{rl}G\left(x\right)& =\frac{2}{1+\sqrt{1-4x}}=\sum _{n=0}^{\mathrm{\infty }}{C}_n{x}^n\\ & =1+x+2x^2+5x^3+14x^4+42x^5+\cdots .\end{array}$(1) ) satisfy (9) $\begin{array}{rl}{G}^{\left(n\right)}\left(x\right)& =\frac{(n-1)!}{(1-4x{)}^n}\sum _{k=1}^{n}k\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)\\ & \times (1-4x{)}^{k/2}{G}^{k+1}(x).\end{array}$(9)

Proof.

This proof is a slight modification of the first part in the second proof of [21, Theorem 1.1].

Taking $f\left(u\right)=2/(1+u)$ and $u=h\left(x\right)=\sqrt{1-4x}$ in the formula (6(6) $\begin{array}{rl}\frac{{\mathrm{d}}^n}{\mathrm{d}{t}^n}f\circ h\left(t\right)& =\sum _{k=0}^n{f}^{\left(k\right)}\left(h\right(t\left)\right){\mathrm{B}}_{n,k}\\ & \times \left(h^{\prime }\left(t\right),h^{″}\left(t\right),\dots ,h^{(n-k+1)}\left(t\right)\right)\end{array}$(6) ) and utilizing the identity (7(7) $\begin{array}{rl}& {\mathrm{B}}_{n,k}\left(ab{x}_1,a{b}^2{x}_2,\dots ,a{b}^{n-k+1}{x}_{n-k+1}\right)\\ & =a^k{b}^n{\mathrm{B}}_{n,k}(x_1,x_2,\dots ,x_{n-k+1}),\end{array}$(7) ) yield $\begin{array}{rl}{G}^{\left(n\right)}\left(x\right)& =2\sum _{k=0}^n(-1{)}^k\frac{k!}{(1+u{)}^{k+1}}{\mathrm{B}}_{n,k}\left(-\frac{2}{(1-4x{)}^{1/2}},\right.\\ & -\frac{2^2}{(1-4x{)}^{3/2}},\dots ,\\ & -\left.\frac{2^{n-k+1}\left[2\right(n-k+1)-3]!!}{(1-4x{)}^{\left[2\right(n-k+1)-1]/2}}\right)\\ & =2\sum _{k=0}^n(-1{)}^k\frac{k!}{{\left(1+\sqrt{1-4x}\right)}^{k+1}}(-1{)}^k{2}^n\\ & \times \frac{(1-4x{)}^{k/2}}{(1-4x{)}^n}\\ & \times {\mathrm{B}}_{n,k}\left((-1)!!,1!!,\dots ,\left[2\right(n-k)-1]!!\right)\\ & =\frac{2^{n+1}}{(1-4x{)}^n}\sum _{k=0}^n\frac{k!{\left(\sqrt{1-4x}\right)}^k}{{\left(1+\sqrt{1-4x}\right)}^{k+1}}\\ & \times {\mathrm{B}}_{n,k}\left((-1)!!,1!!,\dots ,\left[2\right(n-k)-1]!!\right)\end{array}$ for $n\in \mathbb{N}$. Further making use of the formula (8(8) $\begin{array}{rl}& {\mathrm{B}}_{n,k}\left(\right(-1)!!,1!!,3!!,\dots ,[2(n-k)-1]!!)\\ & =\left[2\right(n-k)-1]!!\left(\genfrac{}{}{0em}{}{2n-k-1}{2(n-k)}\right),\end{array}$(8) ) and simplifying arrive at $\begin{array}{rl}{G}^{\left(n\right)}\left(x\right)& =\frac{2^{n+1}}{(1-4x{)}^n}\sum _{k=1}^{n}k!\left[2\right(n-k)-1]!!\\ & \times \left(\genfrac{}{}{0em}{}{2n-k-1}{2(n-k)}\right)\frac{(1-4x{)}^{k/2}}{{\left(1+\sqrt{1-4x}\right)}^{k+1}}\\ & =\frac{2^{n+1}}{(1-4x{)}^n}\sum _{k=1}^{n}k\frac{(2n-k-1)!}{2^{n-k}(n-k)!}\\ & \times \frac{(1-4x{)}^{k/2}}{{\left(1+\sqrt{1-4x}\right)}^{k+1}}\\ & =\frac{(n-1)!}{(1-4x{)}^n}\sum _{k=1}^{n}k\left(\genfrac{}{}{0em}{}{2n-k-1}{n-k}\right)\\ & \times (1-4x{)}^{k/2}{G}^{k+1}(x)\\ & =\frac{(n-1)!}{(1-4x{)}^n}\sum _{k=1}^{n}k\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)\\ & \times (1-4x{)}^{k/2}{G}^{k+1}(x).\end{array}$ The proof of Theorem 3.1 is complete.

Remark 3.1

Comparing (2(2) $G^{\left(n\right)}\left(x\right)=\sum _{i=1}^n{a}_i\left(n\right)(1-4x{)}^{-(2n-i)/2}{G}^{i+1}(x),n\in \mathbb{N}$(2) ) with (9(9) $\begin{array}{rl}{G}^{\left(n\right)}\left(x\right)& =\frac{(n-1)!}{(1-4x{)}^n}\sum _{k=1}^{n}k\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)\\ & \times (1-4x{)}^{k/2}{G}^{k+1}(x).\end{array}$(9) ) derives $\begin{array}{rl}{a}_k\left(n\right)& =(n-1)!\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)\\ & =\frac{(2n-k-1)!}{(n-k)!},n\ge k\ge 1.\end{array}$ This expression is quite simpler, more easily remembered, more possibly understood, more readily computed, more significant, and more meaningful than the one in (3(3) $\begin{array}{rl}{a}_i\left(n\right)& =2^{n-i}i!\sum _{k_{i-1}=0}^{n-i}\sum _{k_{i-2}=0}^{n-i-k_{i-1}}\cdots \sum _{k_1=0}^{n-i-k_{i-1}-\cdots -k_2}\\ & \times \left(2n-2\sum _{j=1}^{i-1}{k}_j-2i-1\right)!!\\ & \times \prod _{\ell =1}^{i-1}{⟨2n-2\sum _{j=\ell +1}^{i-1}{k}_j-2i-1+\ell ;2⟩}_{k_{\ell }}\end{array}$(3) ).

Theorem 3.2

For $n\in \mathbb{N},$ the power to n and the derivatives of the generating function $G\left(x\right)$ defined in (1(1) $\begin{array}{rl}G\left(x\right)& =\frac{2}{1+\sqrt{1-4x}}=\sum _{n=0}^{\mathrm{\infty }}{C}_n{x}^n\\ & =1+x+2x^2+5x^3+14x^4+42x^5+\cdots .\end{array}$(1) ) satisfy (10) $\begin{array}{rl}{G}^{n+1}\left(x\right)& =\frac{(-1{)}^n}{(1-4x{)}^{n/2}}\sum _{k=1}^n\frac{(-1{)}^k}{k!}\\ & \times \left(\genfrac{}{}{0em}{}{k}{n-k}\right)(1-4x{)}^k{G}^{\left(k\right)}(x).\end{array}$(10)

Proof.

The derivative formula (9(9) $\begin{array}{rl}{G}^{\left(n\right)}\left(x\right)& =\frac{(n-1)!}{(1-4x{)}^n}\sum _{k=1}^{n}k\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)\\ & \times (1-4x{)}^{k/2}{G}^{k+1}(x).\end{array}$(9) ) can be rearranged as $\begin{array}{rl}& (-1{)}^{n}n\left[\frac{(4x-1{)}^n}{n!}{G}^{\left(n\right)}\left(x\right)\right]\\ & =\sum _{k=1}^n\left(\genfrac{}{}{0em}{}{2n-k-1}{n-1}\right)(-1{)}^{k}k\\ & \times \left[(-1{)}^k(1-4x{)}^{k/2}{G}^{k+1}\left(x\right)\right],n\in \mathbb{N}.\end{array}$ Considering Lemma 2.4 leads straightforwardly to $\begin{array}{rl}& (-1{)}^n(1-4x{)}^{n/2}{G}^{n+1}\left(x\right)\\ & =\sum _{k=1}^n\left(\genfrac{}{}{0em}{}{k}{n-k}\right)\frac{(4x-1{)}^k}{k!}{G}^{\left(k\right)}\left(x\right),n\in \mathbb{N}.\end{array}$ The proof of Theorem 3.2 is complete.

Remark 3.2

Comparing (4(4) $n!G^{n+1}\left(x\right)=\sum _{i=0}^{\lfloor n/2\rfloor }{b}_i\left(n\right)(1-4x{)}^{n/2-i}{G}^{(n-i)}(x),n\in \mathbb{N}$(4) ) with (10(10) $\begin{array}{rl}{G}^{n+1}\left(x\right)& =\frac{(-1{)}^n}{(1-4x{)}^{n/2}}\sum _{k=1}^n\frac{(-1{)}^k}{k!}\\ & \times \left(\genfrac{}{}{0em}{}{k}{n-k}\right)(1-4x{)}^k{G}^{\left(k\right)}(x).\end{array}$(10) ) reveals $b_i\left(n\right)=(-1{)}^i\frac{n!}{(n-i)!}\left(\genfrac{}{}{0em}{}{n-i}{i}\right),0\le i\le ⌊\frac{n}{2}⌋.$ This expression is rather simpler, more easily remembered, more possibly understood, more readily computed, more significant, and more meaningful than the one in (5(5) $b_i\left(n\right)=(-2{)}^i{S}_{n+1-2i,i},1\le i\le ⌊\frac{n}{2}⌋$(5) )!!!

Remark 3.3

This paper is a shortened version of the preprint [23].

Acknowledgments

The authors are grateful to Dr. Professor Taekyun Kim (Kwangwoon University, South Korea) for his sending an electronic copy of his paper [3] to the first author on November 15, 2017 through e-mail. The authors are thankful to anonymous referees for their careful corrections to and valuable comments on the original version of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Feng Qi  http://orcid.org/0000-0001-6239-2968

Yong-Hong Yao  http://orcid.org/0000-0002-0452-785X