gen_func.tex

\section{Generating functions}
\subsection{Definitions, notation}
\begin{align*}
&\nseq{a_n} \ogf \sum_{n \geq 0} a_n x^n\\ 
&D := \lambda f . f' ~~~ (D(f)(x) = f'(x))\\
&xD := \lambda f x . x D(f)(x) ~~~ (xD(f)(x) = xf'(x))\\
&[x^n]F(x) := \text{coef. of $x^n$ in T. expansion of $F(x)$}\\
&\left[\dfrac{x^n}{\alpha}\right]F(x) := \alpha \left[x^n\right]F(x)\\
&\text{($P(n)$ is (finite) polynom)}\\
\end{align*}

\subsection{Basic facts}
\begin{align*}
&\nseq{1} \ogf \sum_{n \geq 0} x^n = \dfrac{1}{1-x}\\
&\nseq{r^n} \ogf \sum_{n \geq 0} r^n x^n = \dfrac{1}{1-rx}\\
&\nseq{P(n)} \ogf \sum_{n \geq 0} P(n) x^n = P(xD) \left(\dfrac{1}{1-x}\right)\\
&\seq{1,2,3,4,5,\ldots} \ogf \sum_{n \geq 0} (n+1) x^n = \dfrac{1}{(1-x)^2}\\
&\nseq{{n \choose q}} \ogf \sum_{n\geq 0}{n \choose q} x^n =  \dfrac{x^q}{(1-x)^{q+1}}\\
&\nseq{{n + m - 1 \choose n}} \ogf \dfrac{1}{(1-x)^m}\\
&\nseq{{c \choose n}} \ogf \sum_{n \geq 0} {c \choose n} x^n = (1+x)^c\\
&\seq{0, 1, \dfrac{1}{2}, \dfrac{1}{3}, \dfrac{1}{4}, \ldots} \ogf \sum_{n \geq 0} \dfrac{1}{n} x^n = \ln \dfrac{1}{1-x}\\
&\seq{0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4}, \ldots} \ogf \sum_{n \geq 1} \dfrac{(-1)^{n+1}}{n} x^n = \ln(1+x) \\
&\nseq{\dfrac{1}{n+1} {2n \choose n}} \ogf \sum_{n \geq 0} \dfrac{1}{n+1} {2n \choose n} x^n = \dfrac{1 - \sqrt{1 - 4x}}{2x} \\
&\nseq{F_n} \ogf \sum_{n \geq 0} F_n x^n = \dfrac{x}{1 - x - x^2} = \dfrac{x}{(x - \phi)(x - \psi)}\\
& \nthroot{q}{1}_{k} = \nthroot{q}{\exp{2\pi i}}_{k} = \exp{\dfrac{2\pi ki}{q}}\\
&\Big[q ~|~ n\Big] = 
\dfrac{1}{q} \sum_{k=0}^{q-1} \left(\nthroot{q}{1}_{k}\right)^n = 
\dfrac{1}{q} \sum_{k=0}^{q-1} \left( \exp{\dfrac{2\pi n i}{q}} \right)^k  \\
\end{align*}

\subsection{GF/sequences transformations}
\textbf{Let $\nseq{a_n} \ogf f(x)$}
\begin{align*}
&\nseq{\alpha a_n + \beta} \ogf \alpha f(x) + \dfrac{\beta}{1-x}\\
&\nseq{P(n) a_n} \ogf P(xD)(f)\\
&\nseq{n a_n} \ogf \sum_{n\geq 0} n a_n x^n = x f'(x) \\
&\seq{0, a_0, a_1, \ldots} \ogf x f(x)\\
&\nseq{a_{n+k}} \ogf \dfrac{f(x) - a_0 - a_1 x - \ldots - a_{k-1} x^{k-1}}{x^k}\\
&\nseq{a_n \Big[q ~|~ n\Big]} \ogf \sum_{n \geq 0} a_{qn} x^{qn} =
\dfrac{1}{q} \sum_{k=0}^{q-1} f\left(x \nthroot{q}{1}_{k} \right)\\
&\seq{a_0, 0, a_2, 0, a_4, \ldots} \ogf \sum_{n\geq 0} a_{2n}x^{2n} = \dfrac{f(x) + f(-x)}{2}\\
&\seq{a_0, 0, a_1, 0, a_2, 0, \ldots} \ogf f(x^2)\\
&\nseq{\sum_{k=0}^{n} a_k b_{n-k}} \ogf fg ~~~ \text{(if $\nseq{b_n} \ogf g$)}\\
&\nseq{\sum_{n_1 + n_2 + \ldots + n_k = n} a_{n_1} a_{n_2} \ldots a_{n_k}} \ogf f^k\\
&\nseq{\sum_{k=0}^n a_k} \ogf \dfrac{f}{1-x}\\
&D \sum_{n\geq 0} a_n x^n = \sum_{n\geq 0} n a_n x^{n-1}
\end{align*}
$\dfrac{1}{f}$ exists and is unique, iff $f(0) \neq 0$ ($ \Leftrightarrow [x^0]f \neq 0$)

$f(g(x))$ exists, if $g(0) = 0$ or $f(x)$ has finite Taylor expansion.

\subsection{Method for destroying recurrences}
\begin{enumerate}
  \item prerequisites: no free variables, known conditions for reccurent relations
  \item define GF
  \item multiply both sides of recurrent relation with $x^n$, sum for all possible $n$
  \item rewrite both sides as functions of GF
  \item solve equation for GF
  \item find coefficient for $x^n$ in Taylor expansion of GF
\end{enumerate}

\subsection{\uppercase{Snake oil} method for destroying sums}
\begin{enumerate}
  \item identify free variable in given sum, define given sum as function $f(n)$
  \item let $F(x) := \sum_{n \geq 0} f(n) x^n$
  \item change order of summation, find closed form of inner sum
  \item find $[x^n]F(x)$
\end{enumerate}