Proof involving generating function

Question

The following is part of a proof that the number of ways of associating a product with $n$ terms (different ways of inserting parentheses) is $$ a_1 = 1,\ a_n = \frac{1}{n} \binom{2n-2}{n-1},$$ and the relationship$$ a_{n+1} = a_1a_n + a_2a_{n-1} + a_3a_{n-2} + \cdots + a_na_1$$ is already established.

The proof starts with the generating function $$f_A(x) = \sum_{n=1}^\infty a_nx^n,$$ then by the relationship, $$f_A(x) = x + \sum_{n=2}^\infty (a_1a_{n-1} + \cdots + a_{n-1}a_1)x^n.$$ I am unclear about the next step: $$f_A(x) = x + \left(\sum_{n=1}^\infty a_nx^n\right)\left(\sum_{n=1}^\infty a_nx^n\right).$$

I tried using an upper bound of three in each expression. For the first expression I obtained $$a_1^2x^2 + 2a_1a_2x^3.$$ For the second expression I obtained $$a_1^2x^2 + 2a_1a_2x^3 + a_2^2x^4 + 2a_2a_3x^5 + a_3^2x^6.$$ As it appears the first two terms are the same. Can we ignore the extra terms as the upper bound approaches infinity?

Answer 1

Instead of truncating each series, perhaps a better way to think about it is the following: what is the coefficient of $x^k$ in $(\sum_{n=1}^\infty a_n x^n)^2 = \sum_{n=1}^\infty \sum_{m=1}^\infty a_n a_m x^{n+m}$? You would have to add all the terms of the form $a_n a_m x^{n+m}$ where $n+m=k$.

Answer 2

For generating functions, the power series are actually formal power series, and the product of two formal power series obeys the following rule (See also here):$$ \left( \sum_{n = 0}^∞ a_n x^n \right)\left( \sum_{n = 0}^∞ b_n x^n \right) = \sum_{n = 0}^∞ \left( \sum_{k = 0}^n a_k b_{n-k} \right) x^n. \tag{1} $$ The intuition behind this rule is that if $\sum\limits_{n = 0}^∞ a_n x^n$ and $\sum\limits_{n = 0}^∞ b_n x^n$ are two power series (not formal ones) that converge absolutely, Merten's theorem implies that the RHS of (1) also converges and (1) holds. As for the reason why the coefficients of $x^n$ on the RHS is $\sum\limits_{k = 0}^n a_k b_{n-k}$, it is easy to see the intuition by looking for the coefficient of $x^n$ on the LHS.

Answer 3

The sketch below

should help to clear that the product of two series, in general, (provided that they are absolutely convergent of course) can be done by summing

• first by "rows" and then by "columns", or
• first by "columns" and then by "rows", or
• first along the inverse "diagonals" and then over them

that is $$ \eqalign{ & \left( {\sum\limits_{1\, \le \,k} {a_{\,k} x^{\,k} } } \right)\left( {\sum\limits_{1\, \le \,j} {b_{\,j} x^{\,j} } } \right) = \cr & = \sum\limits_{1\, \le \,k} {\left( {a_{\,k} x^{\,k} \left( {\sum\limits_{1\, \le \,j} {b_{\,j} x^{\,j} } } \right)} \right)} = \cr & = \sum\limits_{1\, \le \,j} {\left( {\left( {\sum\limits_{1\, \le \,k} {a_{\,k} x^{\,k} } } \right)b_{\,j} x^{\,j} } \right)} = \cr & = \sum\limits_{2\, \le \,q} {\left( {\left( {\sum\limits_{1\, \le \,k} {a_{\,k} b_{\,q - k} } } \right)x^{\,q} } \right)} \cr} $$

Clearly, if you put an upper bound to the sums, that is you limit to a rectangle the infinite grid above, than in summing along the diagonals , if you go over the maximum possible exponent for $x$ you will have some terms missing.

Answer 4

Note that $$ \begin{align} f(x) &=\sum_{n=1}^\infty\color{#C00}{a_n}x^n\tag1\\ &=\color{#C00}{a_1}x+\sum_{n=2}^\infty\color{#C00}{\sum_{k=1}^{n-1}a_ka_{n-k}}x^n\tag2\\ &=x+\left(\sum_{n=1}^\infty a_nx^n\right)^2\tag3\\[9pt] &=x+f(x)^2\tag4 \end{align} $$ Explanation:
$(1)$: $f$ is the generating function for $a_n$
$(2)$: use the recurrence for $a_n$
$(3)$: $a_1=1$ and the Cauchy Product of the sum in $(2)$
$(4)$: $f$ is the generating function for $a_n$

Since, $f(x)^2-f(x)+x=0$, $$ \begin{align} f(x) &=\frac{1-\sqrt{1-4x}}2\tag5\\ &=\sum_{n=1}^\infty\frac1{4n-2}\binom{2n}{n}x^n\tag6 \end{align} $$ Explanation:
$(5)$: apply the Quadratic Formula
$(6)$: apply the Generalized Binomial Theorem

Since $f$ is the generating function for $a_n$, $$ a_n=\frac1{4n-2}\binom{2n}{n}=\frac1n\binom{2n-2}{n-1}\tag7 $$

Answer 5

Let $$f_n = \frac{1}{n} \binom{2n-2}{n-1} = \frac{1}{2n - 1} \binom{2n-1}{n}$$
\begin{align} f(x) &= \sum_{n=1}^\infty f_nx^n\tag{1}\\ &= \sum_{n=1}^\infty \frac{1}{2n - 1} \binom{2n-1}{n}x^n\\ &= \sum_{n=1}^\infty \frac{(2n-2)!}{n!(n-1)!}x^n\\ &= \sum_{n=1}^\infty \frac{1}{n} \binom{2n-2}{n-1}x^n\tag{2}\\ &= \frac{1}{2} - \frac{1}{2}\sqrt{1 - 4x}\\ \end{align}

$$x + \left(\sum_{n=1}^\infty f_nx^n\right)\left(\sum_{n=1}^\infty f_nx^n\right) =x + [f(x)]^2 = f(x)$$

But from equation (1), $$[f(x)]^2 = \sum_{n=2}^\infty\left(\sum_{i=1}^{n-1}f_if_{n-1}\right)x^n$$ Therefore, $$x + \sum_{n=2}^\infty\left(\sum_{i=1}^{n-1}f_if_{n-1}\right)x^n = \sum_{n=1}^\infty f_nx^n$$

---

An observation $f_n = \frac{1}{n} \binom{2n-2}{n-1} = \frac{(2n-2)!}{n!(n-1)!} = C_{n-1}$. Where $C_n$ is the Catalan Number