generating-functions-examples.tex

\section{Examples of generating functions}

In the following sections we study some interesting sequences. Every
section's title shows the sequence under study in that section and its
body contains the building of the relative generating function.

\subsection{$\{c^n\}_{n\in \mathbb{N} }$}
\begin{displaymath}
  \begin{split}
    \mathcal{G} (c^n) = \sum_{n \geq 0}{c^n t^n} &= \sum_{n \geq
      0}{1_n\cdot (ct)^n} = \sum_{n \geq 0}{1_n \cdot (ct)^n}  \\
    &= \mathcal{G} (1_n) \circ (ct) = \ \frac{1}{1-ct} \quad \text{ by
    composition of } \mathcal{G} 
  \end{split}
\end{displaymath}
Doing a simple check with Maxima:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i226) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=1/(1-c*t)$
taylor(b(t),t,0,8);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o227) }
1+c\,t+{c}^{2}\,{t}^{2}+{c}^{3}\,{t}^{3}+{c}^{4}\,{t}^{4}+{c}^{5}\,{t}^{5}+{c}^{6}\,{t}^{6}+{c}^{7}\,{t}^{7}+{c}^{8}\,{t}^{8}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{(-1)^n a_n\}_{n\in \mathbb{N} }$}
\begin{displaymath}
    \mathcal{G} ((-1)^n a_n) = \sum_{n \geq 0}{(-1)^n a_n t^n} = \sum_{n \geq
      0}{a_n (-t)^n} = \mathcal{G} (a_n) \circ (-t) = a(-t)
\end{displaymath}

\subsection{$\{n\}_{n\in \mathbb{N} }$}
\begin{displaymath}
  \mathcal{G} (n) = \mathcal{G} (n\cdot 1_n) = t
  \frac{\partial}{\partial t}\left( \mathcal{G} (1_n) \right) = \frac{t}{{\left( 1-t\right) }^{2}}
  \end{displaymath}
  Doing a little check with Maxima:
  
\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i244) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=1/(1-t)$
fg(t):=t*diff(b(t),t);
fg(t);
taylor(fg(t),t,0,8);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o245) }
\mathrm{fg}\left( t\right) :=t\,\mathrm{diff}\left( \mathrm{b}\left( t\right) ,t\right) 
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o246) }
\frac{t}{{\left( 1-t\right) }^{2}}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o247) }
t+2\,{t}^{2}+3\,{t}^{3}+4\,{t}^{4}+5\,{t}^{5}+6\,{t}^{6}+7\,{t}^{7}+8\,{t}^{8}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{n^2\}_{n\in \mathbb{N} }$}
Using the result of the previous exercise:
\begin{displaymath}
  \mathcal{G} (n^2) = \mathcal{G} (n n) = t
  \frac{\partial}{\partial t}\left( \mathcal{G} (n) \right) = 
  -\frac{{t}^{2}+t}{{t}^{3}-3\,{t}^{2}+3\,t-1}
\end{displaymath}
Just a little check:\\
\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i252) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
snder(t):=t*diff(fg(t),t)$
ratsimp(snder(t));
taylor(snder(t),t,0,8);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o253) }
-\frac{{t}^{2}+t}{{t}^{3}-3\,{t}^{2}+3\,t-1}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o254) }
t+4\,{t}^{2}+9\,{t}^{3}+16\,{t}^{4}+25\,{t}^{5}+36\,{t}^{6}+49\,{t}^{7}+64\,{t}^{8}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{a_n = 1 \text{ if } n \text{ is even }, 0 \text{
    otherwise}\}_{n\in \mathbb{N} }$}

We compare $\mathcal{G}(a_n) $ with $\mathcal{G} (1_n)$:
\begin{displaymath}
  \begin{split}
    \mathcal{G} (a_n) &= 1 + t^2 + t^4 + t^6 + \ldots \\
    \mathcal{G} (1_n) &= 1 + t^1 + t^2 + t^3 + \ldots \\
  \end{split}
\end{displaymath}
So we can compose $\mathcal{G} (1_n)$ which is known with the function
$t^2$ to obtaining $\mathcal{G} (a_n)$:
\begin{displaymath}
  \mathcal{G} (a_n) =  \frac{1}{1-t} \circ t^2 =  \frac{1}{1-t^2} 
\end{displaymath}
Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i8) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=1/(1-t)$
taylor(b(t^2),t,0,10);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o9) }
1+{t}^{2}+{t}^{4}+{t}^{6}+{t}^{8}+{t}^{10}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{a_n = (1,0,0,1,0,0,1,0,0,1,\ldots)\}_{n\in \mathbb{N} }$}

We compare $\mathcal{G}(a_n) $ with $\mathcal{G} (1_n)$ again:
\begin{displaymath}
  \begin{split}
    \mathcal{G} (a_n) &= 1 + t^3 + t^6 + t^9\ldots \\
    \mathcal{G} (1_n) &= 1 + t^1 + t^2 + t^3 + \ldots \\
  \end{split}
\end{displaymath}
So we can compose $\mathcal{G} (1_n)$ which is known with the function
$t^3$ to obtaining $\mathcal{G} (a_n)$:
\begin{displaymath}
  \mathcal{G} (a_n) =  \frac{1}{1-t} \circ t^3 =  \frac{1}{1-t^3} 
\end{displaymath}
Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i10) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
taylor(b(t^3),t,0,10);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o10) }
1+{t}^{3}+{t}^{6}+{t}^{9}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{a_n = (1,0,0,2,0,0,4,0,0,8,\ldots)\}_{n\in \mathbb{N} }$}

We compare $\mathcal{G}(a_n) $ with $\mathcal{G} (2^n)$ again:
\begin{displaymath}
  \begin{split}
    \mathcal{G} (a_n) &= 1 + 2t^3 + 4t^6 + 8t^9\ldots \\
    \mathcal{G} (2^n) &= 1 + 2t^1 + 4t^2 + 8t^3 + \ldots \\
  \end{split}
\end{displaymath}
So we can compose $\mathcal{G} (2^n)$ which is known with the function
$t^3$ to obtaining $\mathcal{G} (a_n)$:
\begin{displaymath}
  \mathcal{G} (a_n) =  \frac{1}{1-2t} \circ t^3 =  \frac{1}{1-2t^3} 
\end{displaymath}
Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i13) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=1/(1-2*t)$
taylor(b(t^3),t,0,15);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o14) }
1+2\,{t}^{3}+4\,{t}^{6}+8\,{t}^{9}+16\,{t}^{12}+32\,{t}^{15}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{a_n =  \frac{1}{n} \}_{n\in \mathbb{N} } \wedge a_0 = 0$}

We try to understand the generating function $\mathcal{G}(a_n) $:
\begin{displaymath}
  \begin{split}
    \mathcal{G} ( \frac{1}{n} ) &= t + \frac{1}{2} t^2 +  \frac{1}{3}
    t^3 +  \frac{1}{4} t^4 + \ldots \\
     \frac{a_{n+1}}{a_n} &=  \frac{n}{n+1} \quad \text{ by ratio of
       consecutive terms}\\
      (n+1)a_{n+1}  &= n a_n
  \end{split}
\end{displaymath}
In order to apply the identity principle, it is required to check if
the equivalence holds for all $n$. But this isn't the case for
$n=0:a_{1} = 1 \not = 0 = a_0$. So we've to augment the second member
with the term $\delta_{n,k}$ such that $\delta_{n,k} = 1 \text{ if }
n=k, 0 \text{ otherwise}$. Augmenting we obtain $(n+1)a_{n+1} = n a_n
+ \delta_{n,0}, \forall n \in \mathbb{N} $, in particular for
$n=0:a_{1} = 1 = 1 = a_0 + \delta_{0,0}$. Now it is possible to apply
the identity principle, calling $b_{n+1} = (n+1)a_{n+1}$ (hence $b_n
=n a_n$ and $b_0 = 0$):
\begin{displaymath}
  \begin{split}
    b_{n+1} &= n a_n + \delta_{n,0} \\
    &\downarrow \\
    \mathcal{G} (b_{n+1}) &= \mathcal{G} (n a_n) + \mathcal{G}
    (\delta_{n,0}) \\
    \frac{\mathcal{G} (b_n) - b_0}{t} &= \mathcal{G} (n a_n) +
    \mathcal{G}
    (\delta_{n,0}) \\
    \frac{\mathcal{G} (n a_n)}{t} &= \mathcal{G} (n a_n) + \mathcal{G}
    (\delta_{n,0}) \\
    \frac{t \frac{\partial}{\partial t}\left( \mathcal{G} (a_n)
      \right) }{t} &= \mathcal{G} (n a_n) + \mathcal{G}
    (\delta_{n,0}) \\
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) &= t
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) + 1 \\
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) &=
    \frac{1}{1-t}
  \end{split}
\end{displaymath}
Integrating both members:
\begin{equation}
  \label{eq:one-above-n-gen-function}
  \mathcal{G} ( \frac{1}{n} ) = \log{ \frac{1}{1-t} }
\end{equation}
Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i15) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=log(1/(1-t))$
taylor(b(t),t,0,13);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o16) }
t+\frac{{t}^{2}}{2}+\frac{{t}^{3}}{3}+\frac{{t}^{4}}{4}+\frac{{t}^{5}}{5}+\frac{{t}^{6}}{6}+\frac{{t}^{7}}{7}+\frac{{t}^{8}}{8}+\frac{{t}^{9}}{9}+\frac{{t}^{10}}{10}+\frac{{t}^{11}}{11}+\frac{{t}^{12}}{12}+\frac{{t}^{13}}{13}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{H_n = \sum_{k=1}^{n}{ \frac{1}{k} } \}_{n\in \mathbb{N}
  } $}

\begin{displaymath}
  \begin{split}
    \mathcal{G} \left(\sum_{k=1}^{n}{ \frac{1}{k} } \right) &=
    \mathcal{G} \left(\sum_{k=1}^{n}{ \frac{1}{k} 1_{n-k} } \right) = \\
    &=\mathcal{G} \left(\frac{1}{n}\right) \mathcal{G} (1_n) \quad
    \text{ by
      convolution of }\mathcal{G}\\
    &= \left (\log{ \frac{1}{1-t}}\right) \frac{1}{1-t} \quad \text{by
      \autoref{eq:one-above-n-gen-function} and
      \autoref{eq:genfun-of-ones-sequence}}
  \end{split}
\end{displaymath}

Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i66) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
harmonic(n) := sum(1/k,k,1,n);
b(t):=log(1/(1-t))*(1/(1-t));
map(harmonic, makelist(n,n,1,10));
taylor(b(t),t,0,10);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o66) }
\mathrm{harmonic}\left( n\right) :=\sum_{k=1}^{n}\frac{1}{k}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o67) }
\mathrm{b}\left( t\right) :=\mathrm{log}\left( \frac{1}{1-t}\right)
\,\frac{1}{1-t}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o68) }
[1,\frac{3}{2},\frac{11}{6},\frac{25}{12},\frac{137}{60},\frac{49}{20},\frac{363}{140},\frac{761}{280},\frac{7129}{2520},\frac{7381}{2520}]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o69) }
t+\frac{3\,{t}^{2}}{2}+\frac{11\,{t}^{3}}{6}+\frac{25\,{t}^{4}}{12}+\frac{137\,{t}^{5}}{60}+\frac{49\,{t}^{6}}{20}+\frac{363\,{t}^{7}}{140}+\frac{761\,{t}^{8}}{280}+\frac{7129\,{t}^{9}}{2520}+\frac{7381\,{t}^{10}}{2520}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{F_{n+2} = F_{n+1} + F_{n} \}_{n\in \mathbb{N}} \wedge
  F_1 = 1 \wedge F_0 = 0 $}

It is possible to apply the \emph{Identity Principle} directly because
the equality $F_{n+2} = F_{n+1} + F_{n} $ holds $\forall n \in
\mathbb{N} $ (would be problem if we formulate the same as $F_{n} =
F_{n-1} + F_{n-2} $ for $n=0$):

\begin{displaymath}
  \begin{split}
    F_{n+2} &= F_{n+1} + F_{n}  \\
    &\downarrow \\
    \mathcal{G} (F_{n+2}) &= \mathcal{G} (F_{n+1}) + \mathcal{G}
    (F_{n}) \\
    \frac{\mathcal{G} (F_n) - F_0 - F_1 t}{t^2} &= \frac{\mathcal{G}
      (F_n) - F_0}{t} + \mathcal{G}
    (F_{n}) \quad \text{ by translation of } \mathcal{G} \\
    \frac{\mathcal{G} (F_n) - t}{t^2} &= \frac{\mathcal{G} (F_n) }{t}
    + \mathcal{G}
    (F_{n}) \\
    \mathcal{G} (F_n) - t &= t \mathcal{G} (F_n) + t^2 \mathcal{G}
    (F_n)    
  \end{split}
\end{displaymath}
Finally we get:
\begin{equation}
  \label{eq:fibonacci-generating-function}
  \mathcal{G} (F_n) = - \frac{t}{t^2 + t - 1} = \frac{t}{1-t-t^2}
\end{equation}

Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i779) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=t/(1-t-t^2)$
map(fib, makelist(n,n,1,10));
taylor(b(t),t,0,10);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o780) }
[1,1,2,3,5,8,13,21,34,55]
\end{math}

\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o781) }
t+{t}^{2}+2\,{t}^{3}+3\,{t}^{4}+5\,{t}^{5}+8\,{t}^{6}+13\,{t}^{7}+21\,{t}^{8}+34\,{t}^{9}+55\,{t}^{10}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{T_{n+3} = T_{n+2} + T_{n+1} + T_{n} \}_{n\in
    \mathbb{N}} \wedge T_2 = 1 \wedge T_1 = 1 \wedge T_0 = 0 $}

It is possible to apply the \emph{Identity Principle} directly because
the equality $T_{n+3} = T_{n+2} + T_{n+1} + T_{n}$ holds $\forall n
\in \mathbb{N} $:

\begin{displaymath}
  \begin{split}
    T_{n+3} &=T_{n+2}+ T_{n+1} + T_{n}  \\
    &\downarrow \\
    \mathcal{G} (T_{n+3}) &= \mathcal{G} (T_{n+2}) + \mathcal{G}
    (T_{n+1}) + \mathcal{G}
    (T_{n}) \\
    \frac{\mathcal{G} (T_n) - T_0 - T_1 t - T_2t^2}{t^3} &=
    \frac{\mathcal{G} (T_n) - T_0 - T_1 t}{t^2} + \frac{\mathcal{G}
      (T_n) - T_0}{t} + \mathcal{G}
    (T_{n}) \quad \text{ by translation of } \mathcal{G} \\
    \frac{\mathcal{G} (T_n) - t - t^2}{t^3} &= \frac{\mathcal{G} (T_n)
      - t}{t^2} + \frac{\mathcal{G} (T_n) }{t} + \mathcal{G}
    (T_{n})\\
    \mathcal{G} (T_n) - t - t^2 &= t(\mathcal{G} (T_n) - t) +
    t^2\mathcal{G} (T_n) + t^3\mathcal{G}
    (T_{n})\\
    \mathcal{G} (T_n) &= \frac{t}{1-t-t^2-t^3
}
  \end{split}
\end{displaymath}

Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i41) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
tribonacci(n):=if is(n=0) then 0 else if is(n=1) then 1 else if
is(n=2) then 1 else tribonacci(n-1)+tribonacci(n-2)+tribonacci(n-3)\$
b(t):=(t/(1-t-t^2-t^3));
map(tribonacci, makelist(n,n,0,9));
taylor(b(t),t,0,9);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o42) }
\mathrm{b}\left( t\right) :=\frac{t}{1-t-{t}^{2}-{t}^{3}}
\end{math}

\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o43) }
[0,1,1,2,4,7,13,24,44,81]
\end{math}

\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o44) }
t+{t}^{2}+2\,{t}^{3}+4\,{t}^{4}+7\,{t}^{5}+13\,{t}^{6}+24\,{t}^{7}+44\,{t}^{8}+81\,{t}^{9}+...
\end{math}
%%%%%%%%%%%%%%%


\subsection{$\{a_n = {{p}\choose{n}} \}_{n \in \mathbb{N} }$}

There isn't a property ready for direct application, so we study the
ratio between consecutive terms:
\begin{displaymath}
  \begin{split}
    \frac{a_{n+1}}{a_n} = \frac{{{p}\choose{n+1}} }{{{p}\choose{n}} }
    &= \frac{p!}{(n+1)!(p-n-1)!} \frac{n!(p-n)!}{p!} = \frac{p-n}{n+1}\\
    &\downarrow \\
    (n+1)a_{n+1} &= (p-n)a_n
  \end{split}
\end{displaymath}
Before applying the \emph{Identity Principle} we check if the
equivalence holds for all $n$, in particular for $n=0: a_1 = p = p =
pa_0$. So we can apply the principle, calling $b_n = n a_n$:

\begin{displaymath}
  \begin{split}
    b_{n+1} &= (p-n)a_n \\
    &\downarrow \\
    \mathcal{G} (b_{n+1}) &= \mathcal{G} ((p-n)a_n)\\
    \frac{\mathcal{G} (b_n) - b_0}{t} &= \mathcal{G} ((p-n)a_n)\\
    \frac{\mathcal{G} (b_n)}{t} &= \mathcal{G} ((p-n)a_n)\\
    \frac{\mathcal{G} (n a_n)}{t} &= \mathcal{G} ((p-n)a_n)\\
    \frac{t\frac{\partial}{\partial t}\left( \mathcal{G} (a_n)
      \right) }{t} &= \mathcal{G} ((p-n)a_n)\\
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) &=
    p\mathcal{G} (a_n) - \mathcal{G} (n a_n)\\
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) &=
    p\mathcal{G} (a_n) - t \frac{\partial}{\partial t}\left(
      \mathcal{G} (a_n) \right)\\
    (1+t)\frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right)
    &=    p\mathcal{G} (a_n) \\
    \frac{a^\prime(t)}{a(t)} &= \frac{p}{1+t} \quad \text{ by calling
    }
    a(t) = \mathcal{G} (a_n)\\
    \log a(t) &= \int{ \frac{p}{1+t}dt} = p log{(1+t)} + c
  \end{split}
\end{displaymath}
We compute the constant $c$ for $t=0: \log 1 = p \log 1 + c$, with
$a(0) = a_0 + 0t+0t^2 + 0t^3+\ldots = 1$, hence $c=0$ .
\begin{displaymath}
  \begin{split}
    \log{a(t)} &= \log{(1+t)}^p\\
    &\downarrow \quad \text{exping both members}\\
    a(t) = \mathcal{G}\left({{p}\choose{n}}\right) &= (1+t)^p
  \end{split}
\end{displaymath}

Simple check:


\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i45) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=p/(1+t);
integrate(b(t),t);
a(t) := (1+t)^p$
curriedBinomial(n):=binomial(p,n)$
map(ratsimp, map(curriedBinomial, makelist(n,n,0,5)));
taylor(a(t),t,0,5);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o45) }
\mathrm{b}\left( t\right) :=\frac{p}{1+t}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o46) }
p\,\mathrm{log}\left( t+1\right) 
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o49) }
[1,p,\frac{{p}^{2}-p}{2},\frac{{p}^{3}-3\,{p}^{2}+2\,p}{6},\frac{{p}^{4}-6\,{p}^{3}+11\,{p}^{2}-6\,p}{24},\\\frac{{p}^{5}-10\,{p}^{4}+35\,{p}^{3}-50\,{p}^{2}+24\,p}{120}]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o50) }
1+p\,t+\frac{\left( {p}^{2}-p\right) \,{t}^{2}}{2}+\frac{\left(
    {p}^{3}-3\,{p}^{2}+2\,p\right) \,{t}^{3}}{6}+\frac{\left(
    {p}^{4}-6\,{p}^{3}+11\,{p}^{2}-6\,p\right)
  \,{t}^{4}}{24}+\frac{\left(
    {p}^{5}-10\,{p}^{4}+35\,{p}^{3}-50\,{p}^{2}+24\,p\right)
  \,{t}^{5}}{120}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{a_n = {{2n}\choose{n}} \}_{n \in \mathbb{N} }$}

There isn't a property ready for direct application, so we study the
ratio between consecutive terms:
\begin{displaymath}
  \begin{split}
    \frac{a_{n+1}}{a_n} = \frac{{{2n+2}\choose{n+1}}
    }{{{2n}\choose{n}} } &= \frac{(2n+2)!}{(n + 1)!(n+1)!}
    \frac{n!n!}{(2n)!} =
    \frac{(2n+2)(2n+1)}{(n+1)^2} = \frac{2(2n+1)}{n+1}\\
    &\downarrow \\
    (n+1)a_{n+1} &= 2(2n+1)a_n
  \end{split}
\end{displaymath}
Before applying the \emph{Identity Principle} we check if the
equivalence holds for all $n$, in particular for $n=0: a_1 = 2 = 2 =
2a_0$ and $a_0=1$. So we can apply the principle, calling $b_n = n
a_n$:

\begin{displaymath}
  \begin{split}
    b_{n+1} &= (n+1)a_{n+1} \\
    &\downarrow \\
    \mathcal{G} (b_{n+1}) &= \mathcal{G} (2(2n+1)a_n)\\
    \frac{\mathcal{G} (b_n) - b_0}{t} &= \mathcal{G} (2(2n+1)a_n)\\
    \frac{\mathcal{G} (b_n)}{t} &= \mathcal{G} (2(2n+1)a_n)\\
    \frac{\mathcal{G} (n a_n)}{t} &= \mathcal{G} (2(2n+1)a_n)\\
    \frac{t\frac{\partial}{\partial t}\left( \mathcal{G} (a_n)
      \right) }{t} &= \mathcal{G} (2(2n+1)a_n)\\
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) &=
    4\mathcal{G} (n a_n) + 2\mathcal{G} (a_n)\\
    \frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right) &= 4 t
    \frac{\partial}{\partial t}\left(
      \mathcal{G} (a_n) \right) + 2\mathcal{G} (a_n)\\
    (1-4t)\frac{\partial}{\partial t}\left( \mathcal{G} (a_n) \right)
    &=    2\mathcal{G} (a_n) \\
    \frac{a^\prime(t)}{a(t)} &= \frac{2}{1-4t} \quad \text{ by calling
    }
    a(t) = \mathcal{G} (a_n)\\
    \log a(t) &= 2\int{ \frac{1}{1-4t}dt} = - \frac{1}{2} log{(1-4t)}
    + c
  \end{split}
\end{displaymath}
We compute the constant $c$ for $t=0: \log 1 = - \frac{1}{2} \log 1 +
c$, with $a(0) = a_0 + 0t+0t^2 + 0t^3+\ldots = 1$, hence $c=0$ .
\begin{displaymath}
  \begin{split}
    \log{a(t)} &= \log{\frac{1}{\sqrt{1-4t}}}\\
    &\downarrow \\
    a(t) &= \frac{1}{\sqrt{1-4t}}
  \end{split}
\end{displaymath}

Finally we have found:
\begin{equation}
  \label{eq:binomial-coefficient-gen-fun}
  \mathcal{G} \left({{2n}\choose{n}} \right) =
  \frac{1}{\sqrt{1-4t}}
\end{equation}
Simple check:


\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i63) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=2/(1-4*t);
integrate(b(t),t);
a(t) := 1/sqrt(1-4*t)$
curriedBinomial(n):=binomial(2*n,n)$
map(ratsimp, map(curriedBinomial, makelist(n,n,0,5)));
taylor(a(t),t,0,5);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o63) }
\mathrm{b}\left( t\right) :=\frac{2}{1-4\,t}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o64) }
-\frac{\mathrm{log}\left( 1-4\,t\right) }{2}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o67) }
[1,2,6,20,70,252]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o68) }
1+2\,t+6\,{t}^{2}+20\,{t}^{3}+70\,{t}^{4}+252\,{t}^{5}+...
\end{math}
%%%%%%%%%%%%%%%

\subsection{$\{a_n = \frac{1}{n+1} {{2n}\choose{n}} \}_{n \in
    \mathbb{N} }$}

\begin{displaymath}
  \begin{split}
    \mathcal{G} ( \frac{1}{n+1} {{2n}\choose{n}}) &= \frac{1}{t}
    \int{\mathcal{G} ({{2n}\choose{n}} )dt} \quad \text{by \autoref{eq:n-plus-one-a-n-gen-fun}}\\
    &= \frac{1}{t} \int{ \frac{1}{\sqrt{1-4t}} dt} \quad \text{by
      \autoref{eq:binomial-coefficient-gen-fun}}
  \end{split}
\end{displaymath}
Calling $\sqrt{1-4t} = y$ follows $t = \frac{1-y^2}{4} $ and $dt = -
\frac{1}{2}y dy $, so:
\begin{displaymath}
  \begin{split}
    &= \frac{1}{t} \int_0^t{ \frac{1}{y}\left( - \frac{1}{2}y\right)
      dy} = -\frac{1}{2t} \int_0^t{ dy} = -\frac{1}{2t}
    \left[y\right]_0^t = -\frac{1}{2t} \left[\sqrt{1-4t}\right]_0^t\\
    &= -\frac{1}{2t}(\sqrt{1-4t} - 1) = \frac{1- \sqrt{1-4t}}{2t}
  \end{split}
\end{displaymath}

Simple check:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i167) 
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
b(t):=(1-sqrt(1-4*t))/(2*t)$
catalan(n):=binomial(2*n,n)/(n+1)$
map(catalan, makelist(n,n,0,10));
taylor(b(t),t,0,10);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o169) }
[1,1,2,5,14,42,132,429,1430,4862,16796]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o170) }
1+t+2\,{t}^{2}+5\,{t}^{3}+14\,{t}^{4}+42\,{t}^{5}+132\,{t}^{6}+429\,{t}^{7}+1430\,{t}^{8}+4862\,{t}^{9}+16796\,{t}^{10}+...
\end{math}
%%%%%%%%%%%%%%%