4.7 Catalan and Generating Function
\(sCat(s)=\frac{1}{2}\pm\sqrt{\frac{1}{4}-s}\) (*)
We know there are possible square roots of \(\frac{1}{4}-s\)
They differ by multiplication by \(-1\)
We need to choose one of them, from tutorial we know \(\sqrt{\frac{1}{4}-s}=\frac{1}{2}+...\) or \(-\frac{1}{2}+...\)
Since in the left hand side of (*), there is \(s\), thus the right hand side should be divisible by \(s\), thus we choose \(\frac{1}{2}+...\)
Definition
Let \(\alpha\in \mathbb{C}\), define \((1+s)^{\alpha}=\sum_{n=0}^{\infty}\binom{\alpha}{n}s^{n}=\sum_{n=0}^{\infty}\frac{\left(\alpha\right)_{n}}{n!} s^{n}\) where \((\alpha)_{n}= \begin{cases} 1,n=0 \\ \alpha(\alpha-1)...(\alpha-n+1),n>0\text{ with n terms} \end{cases}\)
Justification of this notation
Proposition
\(\forall \alpha,\beta\in\mathbb{C}\), we have \((1+s)^\alpha (1+s)^\beta=(1+s)^{\alpha\beta}\).
Proof (\((fg)=\sum_{n=0}^{\infty}(\sum_{k=0}^{n}f_{k}g_{n-k})s^{n}\))
We want to prove that \(\forall \alpha,\beta\in \mathbb{C}\), \(\frac{(\alpha+\beta)_{n}}{n!}= \sum_{k=0}^{n}\frac{(\alpha)_{k}}{k!}\frac{(\beta)_{n-k}}{(n-k)!}\)
These two are polynomials in \(\alpha\) and \(\beta\).
For a fixed \(\beta\), it is a polynomial of degree n in \(\alpha\).
Take \(\beta \in \mathbb{N}\). For \(\alpha \in \mathbb{N}\), this equality reduces to \(\binom{\alpha+\beta}{n} = \sum_{k=0}^{n} \binom{\alpha}{k} \binom{\beta}{n-k}\).
For a fixed \(\beta \in \mathbb{N}\) these polynomials have the same value in \(\alpha = 1, 2, 3, ...\)
\(\Rightarrow\) For a fixed \(\beta \in \mathbb{N}\) these polynomials are the same.
Consider the both parts as polynomials in \(\beta\) (keeping \(\alpha\) as a parameter). The both parts are the same for \(\beta = 1, 2, 3, 4, 5...\)
\(\Rightarrow\) They are the same as polynomials.
Example
Recall: \((1+s)^{n}=\sum_{k=0}^{\infty}\binom{n}{k}s^{k}=\sum_{k=0}^{\infty}\frac{\left(n\right)_{k}}{k!} s^{k}\) when \(n\in\mathbb{C}\)
E.g.: \((1+s)^{\frac{1}{2}}(1+s)^{\frac{1}{2}}=(1+s)^1\) where \((1+s)^{\frac{1}{2}}\) is a square root of \(1+s\)
\((1+s)^{\frac{1}{2}}=1+\frac{1}{1!}s + \frac{(\frac{1}{2})(-\frac{1}{2})}{2!}s^{2} + \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})}{3!}s^{3} + \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})(-\frac{5}{2})}{4!} s^{4} + ... + (-1)^{n+1}\frac{(2n-3)!!}{2^{n} \cdot n!}s^{n}\)
where \((2n)!! = (2n)(2n-2)(2n-4)...2\). \(\leftarrow\) even factors only
And \((2n+1)!! = (2n+1)(2n-1)(2n-3)...3\cdot 1\). \(\leftarrow\) odd factors only.
Here, \(Cat(s)=\frac{1-\sqrt{1-4s}}{2s}\), by the proposition, we know that
Then we get \(Cat_n=\frac{\frac12\frac12\frac32...\frac{2n-1}{2}\cdot4^{n+1}}{2(n+1)!}\cdot\frac{n!}{n!}\) \(=\frac{1}{n+1}\binom{2n}{n}\) using \((2n-1)!!=\frac{2n!}{2^n\cdot n}\)
This \(Cat_n\) is the coefficients of \(s^n\)
Fibonacci numbers
Suppose we have a sequence defined by \(f_0=f_1=1\), \(\forall n\geq 0,f_{n+2}=f_{n+1}+f_n\)
Introducing the generating function. \(Fib(s)=\sum^\infty_{n=0}f_n\cdot s^n\)
Slogan: Arithmetic relations for the coefficients translate to algebraic relations for the corresponding generating function
\(Fib(s)=f_0+f_1s+f_2s^2+...\)
\(s\cdot Fib(s)=\,\,\,\,\,\,f_{0}s+f_{1}s^2+f_{2}s^{3}+...\)
\(s^2\cdot Fib(s)=\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,f_{0}s^2+f_{1}s^{3}+f_{2}s^{4}+...\)
If we consider \(Fib(s)-s\cdot Fib(s)-s^{2}\cdot Fib(s)=f_0+(f_1-f_0)s+(f_2-f_1-f_0)s^2+(f_3-f_2-f_1)s^3+...\)
\(=1+0+0+0+...\)
So \(Fib(s)-s\cdot Fib(s)-s^2 Fib(s)=1\) \(\iff\) \((1-s-s^2)Fib(s)=1\)
\(\iff\)\(Fib(s)=\frac{1}{1-s-s^2}\)
We say that the generating function \(F(s)\) is rational if \(F(s)=\frac{P(s) }{Q(s)}\) where the both \(P(s)\) and \(Q(s)\) are polynomials
Fact: Partial fraction decomposition of rational functions
\(P(s),\deg P(s)=p,Q(s),\deg Q(s)=q\) admits a decomposition \(Q(s)=\prod^j_{l=1}G_l^{k_l}\)
Where \(G_l\) is a linear polynomia
l say \(\beta(s-\alpha_l)\)
Then there exists the unique polynomial \(H(s)\) of degree \(\max(-1,p-q)\) where degree \(-1\) means it is \(0\)
And complex numbers \(b_{lm},l=1,...,j,m=1,...,k_l\) such that \(\frac{P(s)}{Q(s)}=H(s)+\sum_{l=1}^{j}\sum_{n=1}^{k_{l}}\frac{b_{lm}}{G_{l}^{m}}\)
Find the roots of \((1-s-s^2)=0\)
\(s_{1}=\frac{-1+\sqrt{5}}{2},s_{2}=\frac{-1-\sqrt{5}}{2}\) (Vieta \(\Rightarrow s_{1}s_{2}=-1\))
Then \(1-s-s^2=\alpha(s-s_1)(s-s_2)\)
We need to find the coefficients: \(\frac{1}{1-s-s^2}=\frac{b_1}{s-s_1}+\frac{b_2}{s-s_2}\)
We get \(b_{1}=-1,b_{2}=1,\alpha=\frac{1}{\sqrt5}\)
\(\frac{1}{1-s-s^{2}}=\frac{1}{\sqrt{5}}(\frac{1}{s-s_{2}}-\frac{1}{s-s_{1}})=\frac{1}{\sqrt{5}s_{1}} (1+\frac{s}{s_{1}}+\frac{s^{2}}{s_{1}^{2}}+\frac{s^{3}}{s_{1}^{3}}+...)-\frac{1}{\sqrt{5}s_{2}}(1+\frac{s}{s_{2}}+\frac{s^{2}}{s_{2}^{2}}+\frac{s^{3}}{s_{2}^{3}} +...)\) since \(\frac{1}{s-s_{i}}=-\frac{1}{s_{i}}\frac{1}{1-\frac{s}{s_{i}}}\)
\(\sum_{n=0}^\infty \frac{1}{\sqrt{5}}(s_1^{-1-n}-s_2^{-1-n})s^n\) then use Vieta \(=\sum_{n=0}^\infty \frac{(-1)^{n}}{\sqrt{5}}(s_1^{n+1}-s_2^{n+1})s^n\).
Finally, \(f_n = \frac{(-1)^n}{\sqrt{5}} \left( \left(\frac{-1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{-1-\sqrt{5}}{2}\right)^{n+1} \right)\)
The structure theorem for linear recurrences with constant coefficients
\(k\in \N\), fix \(f_{0},f_{1},...,f_{k-1}\) are fixed numbers (just numbers)
Another collection \(c_1,...,c_k\) of fixed numbers
And a sequence defined by the recurrences
\(f_{n+k}=c_1f_{n+k-1}+c_2f_{n+k-2}+...+c_kf_n\) for all \(n>0\)
Here we can take Fibonacci numbers as an example (\(c_{1}=c_{2}=1\))
Then the generating function \(F(s)=\sum^\infty_{n=0}f_ns^n\) is rational. \(F(s)=\frac{P(s)}{Q(s)}\) where \(\deg Q(s)=k,\deg P(s)\leq k-1\)
\(\,\,\,\,\,+F(s) = f_{0}- f_{1}s + f_{2}s^{2}+ ... + f_{k}s^{k}+ ...\)
\(-c_{1}s F(s) = c_{1}f_{0}s + c_{1}f_{1}s^{2}+ ... + c_{1}f_{k-1}s^{k}+ . ..\)
\(-c_{2} s^{2} F(s) = \quad \quad \,\,\,\,\,\,c_{2} f_{0} s^{2} + ... + c_{2} f_{k-2}s^{k} + ...\)
\(...\)
\(-c_{k}s^{k}F(s)=\quad\quad\quad\quad\quad\quad\quad\,\,\,...+c_{k}f_{0}s^{k}\)
\(\Rightarrow (1 - c_1 s - ... - c_k s^k) F(s) = P(s) \Rightarrow F(s) = \frac{P(s)}{1 - c_1 s - c_2 s^2 - ... - c_k s^k}\) where \(P(s)=f_{0}+(f_{1}-c_{1}f_{0})s+(f_{2}-c_{1}f_{1}-c_{2}f_{0})s^{2}+\cdots\) plus until \(k-1\)