Skip to content

4.9 Generating functions

  1. Find the inverse of the formal power series from \(\mathbb{C}[[s]]\). Express the answer in the form \(\sum_{k=0}^{\infty} c_k s^k\):

    • \(s^{2} - 3s + 2\);

    \(\frac{1}{{}{}s^{2}-3s+2}=\frac{A}{s-1}+\frac{B}{s-2}\), then \(A=-1,B=1\)​

    Thus \(\frac{1}{{}{}s^{2}-3s+2}=-\frac{1}{s-1}+\frac{1}{s-2}\). And \(\frac{1}{s-2}=-\frac{1}{2}\frac{1}{(1-\frac{s}{2})}=-\frac{1}{2}[1+\frac{s}{2}+(\frac{s}{2})^2+...]\)

    \(-\frac{1}{s-1}=\frac{1}{1-s}=1+s+s^2+s^3+...\)​

    Thus \(\frac{1}{s^{2}-3s+2}=\sum_{n=0}^{\infty}s^n(1-\frac{1}{2^{n+1}})\)​ * \(s^{2} - 4s + 4\);

    \(\frac{1}{s^2 - 4s + 4} = \frac{1}{(s-2)^2}\)

    \(\frac{1}{(s-2)^2} = \frac{1}{4} \frac{1}{(1-\frac{s}{2})^2} = \frac{1}{4} \sum_{n=0}^\infty (n+1) (\frac{s}{2})^n\) because

    By formula: \(\frac{1}{(1-s)^{2}}= \sum_{n=0}^{\infty}\binom{-2}{n}(-s)^{n}\)
    What is \(\binom{-2}{n}\)?

    \(\binom{-2}{0} = 1\), \(\binom{-2}{1} = \frac{-2}{1!}\), \(\binom{-2}{2} = \frac{(-2)(-3)}{2!}\), \(\binom{-2}{3} = \frac{(-2)(-3)(-4)}{3!}\)
    ​\(\binom{-2}{n}= (-1)^{n} \frac{(n+1)!}{n!}= (-1)^{n}(n+1)\)

    \(\frac{1}{(1-s)^2} = \sum_{n=0}^{\infty}(n+1) s^{n}\) * \(s^2 + 1\).

    \(\frac{1}{1+s^{2}}=\sum_{n=0}^{\infty}(-1)^{n}s^{2n}\)

    \(\frac{1}{1+s^{2}}= \frac{A}{s-i}+ \frac{B}{s+i}\)​
    ​\(\frac{1}{2i}=A\)
    ​\(\frac{1}{-2i}=B\)

    \(\frac{1}{1+s^{2}}=\frac{1}{2i}\frac{1}{s-i}-\frac{1}{2i}\frac{1}{s+i}\) \(=\frac{1}{2i}(\frac{1}{1-\frac{s}{i}})+\frac{1}{2}(\frac{1}{(\frac{s}{i})+1})\)
    ​\(=\frac{1}{2}\sum_{n=0}^{\infty}s^{n}\left(\frac{1}{i^{n}}+\left(-1\right)^{n}\frac{1}{i^{n}} \right)=\frac{1}{2}\sum_{n=0}^{\infty}s^{2n}((-1)^{n}+(-i)^{n})=\sum_{n=0}^{\infty} s^{2n}(-1)^{n}\)

  2. Find the generating functions for the sequences (hint: recall the explicit formula for the coefficients of \((1-s)^{k}\) with \(k < 0\))

    image​

    • \(a_k = k\) for \(k \geq 0\);
    • \(a_k = 2k^2\) for \(k \geq 0\);
    • \(a_k = 2^k k^2, k \geq 0\).

    image​

    image​

    image​

  3. Find the generating functions and explicit expressions for the sequences given by recurrence relations:

    • \(a_{n+3} = -3a_{n+2} - 3a_{n+1} - a_n\), \(a_{0}=1,a_{1}=a_{2}=0\)
    • \(a_{n+3}=\frac{3}{2}a_{n+2}-\frac{1}{2}a_{n}\), \(a_{0}=0,a_{1}=1,a_{2}=2\).

  4. Prove, that the coefficients of any rational generating function with a denominator of degree \(q \in \N\) eventually satisfy a linear recurrence relation with constant coefficients.

‍