3.31 Recursive Formulas and Generating Functions

Catalan Numbers Problem

​

What is the number of paths of a square \(n\times n\) lattice such that they do not go above the main diagonal?

Solution

Let's \(Cat_n\) be | paths with this condition on the \(n\times n\) square |

\(Cat_0=1,Cat_1=1,Cat_2=2,...\)

Recursion: \(Cat_{n+1}=Cat_{n+1}(Cat_n,Cat_{n-1},...,Cat_0)\)

Paths still can touch the diagonal, but can not pierce it

Let \(Cat^k_{n+1}\) be the set of paths such that they touch the diagonal at the \((0,0),(k,k)\) but not in any intermedia points where \(k=1,...,n+1\)

Fix k: All the paths from \(Cat^{k}_{n+1}\) do not go above the diagonal \(y=x-1\) in the square \((k-1)\times(k-1)\)

​

By the product principle, \(Cat_{n+1}^{k}=Cat_{k-1}Cat_{n-k+1}\). By addition principle, \(Cat_{n+1}=\sum_{k=1}^{n+1}Cat_{k-1}Cat_{n-k+1}=\sum_{j=0}^{n}Cat_{j}Cat_{n-j}\)

Example

Then \(Cat_0=1,Cat_1=1,Cat_2=2,Cat_3=Cat_2Cat_0+Cat_1Cat_1+Cat_0Cat_2=5\)

---

Introduce: \(Cat(s)=Cat_0+Cat_1s+Cat_2s^2+...=\sum^\infty_{n=0}Cat_ns^n\)

A Taylor expansion of a criterium function

What equation should \(Cat(s)\) satisfy to enjoy the recursion we have?

Let's compute \(Cat^2(s)=Cat_0Cat_0+(Cat_1Cat_0+Cat_0Cat_1)s+(Cat_2Cat_0+Cat_1Cat_1+Cat_0Cat_2)s^2+...=Cat_1+Cat_2s+Cat_3s^2+...\)

Then \(sCat^{2}(s)=Cat_{1}s+Cat_{2}s2+Cat_{3}s^{3}+...\)

Then \(sCat^{2}(s)+Cat_{0}=Cat_{0}+Cat_{1}s+Cat_{2}s2+Cat_{3}s^{3}+...=Cat\left(s\right )\)

Proposition

\(sCat^2(s)+1=Cat(s)\)

Then \(s^2Cat^2(s)-sCat(S)+s=0\), then \((sCat(s)-\frac{1}{2})^2+s-\frac{1}{4}=0\)

Then \(sCat(s)=\frac{1}{2}\pm\sqrt{\frac{1}{4}-s}\)​

Definition

Let \(a_0,a_1,...\) be a (possibly infinite) sequence of numbers. The generating function for this sequence is the formal expression \(a_0+a_1s+a_2s^2+...=\sum^\infty_{n=0}a_ns^n\)

Remark

A generating function is not a function, It doesn't make sense to ask what is the value for, say \(s=3\)?

It doesn't make sense to ask where does this series converge

We declare two generating functions \(\sum^\infty_{n=0}f_ns^n\) and \(\sum^\infty_{n=0}g_ns^n\) to be equal if for any \(n\in \N\cup\{0\}\) we have \(f_n=g_n\)

Operations on generating functions

1. Addition: \(f(s)=\sum^\infty_{n=0}f_ns^n\), \(g(s)=\sum^{\infty}_{n=0}g_{n}s^{n}\). We set \((f+g)(s)=\sum^\infty_{n=0}(f_n+g_n)s^n\), this is the same rule that we have for polynomials

2. Multiplication: \(f(s)=\sum^{\infty}_{n=0}f_{n}s^{n},g(s)=\sum^{\infty}_{n=0}g_{n}s^{n}\), we declare \((f\cdot g)(s)=f_{0}g_{0}+\left(f_{1}g_{0}+f_{0}g_{1}\right)s+\cdots=\sum_{n=0}^{\infty} \left(\sum_{k=0}^{n}f_{k}g_{n-k}\right)s^{n}\)​

Proposition

The introduced operations + and \(\times\) on the set of generating functions are

1. Associativity

2. Commutativity

3. Distributivity

Notation

The set of generating functions provided with the operations + and \(\times\) is denotes \(\mathbb{R}[[s]]\) and is called the ring of formal power series

---

Does there exist a formal power series \(f(s)\) such that \(\forall g(s)\in \R[[s]]\) we have \((gf)(s)=(fg)(s)=g(s)\)?

Yes \(f(s)=1=1+0s+0s^2+...\)

Proposition

Let \(f\in \R[[s]]\) satisfy \(f_0\neq 0\), then \(\exists !g\in \R[[s]]\) such that \((fg)(s)=(gf)(s)=1\)

Such \(g(s)\) is sometimes denoted \(f^{-1}(s)\) or \(\frac{1}{f(s)}\)

Proof

Suppose \(g\) exists: \(g=\sum^\infty_{n=0}g_ns^n\), we know \((fg)(s)=(gf)(s)=1\)

Then \(1+0s+0s^{2}+...=(f\cdot g)(s)=f_{0}g_{0}+\left(f_{1}g_{0}+f_{0}g_{1}\right)s+\cdots =\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}f_{k}g_{n-k}\right)s^{n}\)

Thus \(f_0g_0=1\), then \(g_{0}=\frac{1}{f_{0}}\). Also \(f_1g_0+f_0g_1=0\). This is equation of the type \(ax+b=0\) for \(a\neq 0\)

Also, \(f_2g_0+f_1g_1+f_0g_2=0\)..... This system always has a unique solution: The claim is proven

Example

1. \(f(s)=1-s\). Claim: \(\frac{1}{f(s)}=1+s+s^2+...=\sum^\infty_{n=0}s^n\)

   I claim that \(g(s)=\frac{1}{f(s)}= 1 + s + s^{2} + s^{3} + ... = \sum_{n=0}^{\infty}s^{n} = \frac{1}{1-s}\).

   "the geometric progression"

   Multiply: \(f_0 = 1\), \(f_1 = -1\), \(g_i = 1 \ \forall i = 0, 1, ...\)

   Then \(f_0g_0 = 1\), \(\sum_{k=0}^{n} (f_k g_{n-k}) = 1 \cdot g_n - 1 \cdot g_{n-1} = 0\).

   Claim is proven.

2. \(f(s) = 1 + \frac{s}{1!}+ \frac{s^{2}}{2!}+ \frac{s^{3}}{3!}+ ... = \exp(s) = \sum _{n=0}^{\infty}\frac{s^{n}}{n!}\)

   \(g(s)=f^{-1}(s)=1-\frac{s}{1!}+\frac{s^{2}}{2!}-\frac{s^{3}}{3!}+...=\sum_{n=0}^{\infty} \frac{(-1)^{n}s^{n}}{n!}=\exp(-s)\)

   \(f \circ g = 1\)

   General non-zero power term of \(f\circ g\)\: \(\sum_{k=0}^{n} \frac{1}{k!} \frac{(-1)^{n-k}}{(n-k)!} = 0\), for \(n\) since \(\sum_{k=0}^{n} (-1)^{n-k} \binom{n}{n-k} = 0\)

Substitution

Let \(f(t) = f_0 + f_1t + f_2t^2 + ... = \sum_{n=0}^{\infty} f_n t^n \in \mathbb{R}[[t]]\)

\(g(s) = g_1 s + g_2 s^2 + g_3 s^3 + ... = \sum_{n=1}^{\infty} g_n s^n \in \mathbb{R}[[s]]\).

Define: \(f(g(s)) \in \mathbb{R}[[s]]\).

As follows: \(f(g(s)) = f_0 + f_1 (g(s)) + f_2 (g(s))^2 + ...\)

\(= f_{0} + f_{1} g_{1} s + (f_{1} g_{2} + f_{2} g_{1}^{2}) s^{2} + ...\) (after arrange the same power of term)

Examples

\(\frac{1}{1-t}\) and substitute \(t = -s\).
\(1 + t + t^2 + ... \leadsto 1 - s + s^2 - s^3 + ...\)

\(\exp(t)\) and substitute \(t = -s\), then \(\exp(-s)\).

And so on.

Proposition

Let \(f, g \in \mathbb{R}[[s]]\), \(h \in \mathbb{R}[[s]]\) st. \(h_0 = 0\).

Then \((f+g)(h(s)) = f(h(s)) + g(h(s))\) and \((f \cdot g)(h(s)) = f(h(s)) \cdot g(h(s))\).

If \(f\) is invertible, then \(f^{-1}(h(s)) = (f(h(s)))^{-1}\)