generating-functions-basics.tex

\section{Generating functions basics}

In this section we approach the basis about generating functions topic.

\subsection{Approaching}

The main goal of this section is to manipulate a sequence $\{a_n\}_{n\in
  \mathbb{N} }$ through a function $a(t)$ such that:
\begin{displaymath}
  a(t) = \sum_{n \geq 0}{a_n t^n}
\end{displaymath}

Using $a(t)$ allow us to let $t$ be unbounded and we wont assign any
value to it (it is just a ``placeholder''), it is just a \emph{dummy} variable.

We introduce an operator $\mathcal{G}$ which consume a sequence
$\{a_n\}_{n\in \mathbb{N} }$ and produce a function $a(t)$ as defined
above. In the following examples we experiment a little with Maxima,
which implement $\mathcal{G}$ with the function
\texttt{\color{blue} ggf(s)}, for some sequence $s$.\\

Let $\{a_n = n\}$:\\
\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i109)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
sequence:makelist(n,n,0, 6);
taylor(ggf(sequence), x, 0, 8);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o109) }
[0,1,2,3,4,5,6]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o110) }
x+2\,{x}^{2}+3\,{x}^{3}+4\,{x}^{4}+5\,{x}^{5}+6\,{x}^{6}+...
\end{math}\\
%%%%%%%%%%%%%%%
So $\mathcal{G}(a_n) = a(x)=
x+2\,{x}^{2}+3\,{x}^{3}+4\,{x}^{4}+5\,{x}^{5}+6\,{x}^{6}+...$\\

Let $\{a_n = 1 \text{ if } n \text{ is even }, 0 \text{ otherwise}\}$:\\
\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i105)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
onlyEvenTerms(n):=if is(mod (n,2)=0) then 1 else 0$
sequence:makelist(onlyEvenTerms(n),n,0, 6);
ggfOnlyEvenTerms:ggf(sequence);
taylor(ggfOnlyEvenTerms, x, 0, 12);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o106) }
[1,0,1,0,1,0,1]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o107) }
-\frac{1}{{x}^{2}-1}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o108) }
1+{x}^{2}+{x}^{4}+{x}^{6}+{x}^{8}+{x}^{10}+{x}^{12}+...
\end{math}\\
%%%%%%%%%%%%%%%
So $\mathcal{G}(a_n) =
a(x)=1+{x}^{2}+{x}^{4}+{x}^{6}+{x}^{8}+{x}^{10}+{x}^{12}+...$.\\

Let $\{a_n = 1 \text{ if } n \leq 2,  0 \text{ otherwise}\}$:\\
\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i97)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
onlyFirstThreeTerms(n):=if is(n <= 2) then 1 else 0$
sequence:makelist(onlyFirstThreeTerms(n),n,0, 6);
ggfOnlyFirstThreeTerms:ggf(sequence);
taylor(ggfOnlyFirstThreeTerms, x, 0, 100);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o98) }
[1,1,1,0,0,0,0]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o99) }
{x}^{2}+x+1
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o100) }
1+x+{x}^{2}+...
\end{math}\\
%%%%%%%%%%%%%%%
So $\mathcal{G}(a_n) =a(x)=1+{x}+{x}^{2}$.\\

In the following subsections we'll explore some properties of
$\mathcal{G} $.

\subsection{Linearity of $\mathcal{G} $}
Let $\{a_n\}_{n\in\mathbb{N} }$ and $\{b_n\}_{n\in\mathbb{N} } $ be
two sequences, $a(t)$ and $b(t)$ their formal power series
respectively. Lets sum both of them:
\begin{displaymath}
  \begin{split}
    \mathcal{G} (a_n)+ \mathcal{G} (b_n) &= a_0 + a_1 t
    + a_2 t^2 + \ldots + a_n t^n + \ldots \\
    &+ b_0 + b_1 t + b_2 t^2 + \ldots + b_n t^n + \ldots =\\
    &= (a_0 + b_0) + (a_1+b_1) t + (a_2 + b_2) t^2 + \ldots +
    (a_n+b_n) t^n + \ldots =\\
    &= \mathcal{G}(a_n + b_n)
  \end{split}
\end{displaymath}
It is possible to generalize, obtaining:
\begin{displaymath}
  \begin{split}
    \alpha\mathcal{G}(a_n) &= \mathcal{G}(\alpha a_n)\\
    \alpha\mathcal{G}(a_n) +  \beta\mathcal{G}(b_n) &=
    \mathcal{G}(\alpha a_n + \beta b_n)
  \end{split}
\end{displaymath}
So $\mathcal{G}$ is a \emph{linear operator}.

\subsection{Convolution of $\mathcal{G} $}

Let $\{a_n\}_{n\in\mathbb{N} }$ and $\{b_n\}_{n\in\mathbb{N} } $ be
two sequences, $a(t)$ and $b(t)$ their formal power series
respectively. We study the product $a(t)b(t)$ with Maxima:\\
\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i190)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
makeSequence(t,j):=sum (j[i]*t^i, i, 0, inf);
as:taylor(makeSequence(t,a), t, 0, 3);
bs:taylor(makeSequence(t,b), t, 0, 3);
as*bs;
sum ((sum(a[k]*b[n-k],k,0,n))*t^n, n, 0, inf);
taylor(sum((sum(a[k]*b[n-k],k,0,n))*t^n,n,0,inf), t, 0, 3);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o190) }
\mathrm{makeSequence}\left( t,j\right) :=\sum_{i=0}^{\infty }{j}_{i}\,{t}^{i}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o191) }
{a}_{0}+{a}_{1}\,t+{a}_{2}\,{t}^{2}+{a}_{3}\,{t}^{3}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o192) }
{b}_{0}+{b}_{1}\,t+{b}_{2}\,{t}^{2}+{b}_{3}\,{t}^{3}+...
\end{math}\\
\begin{math}\displaystyle
  \parbox{8ex}{\color{labelcolor}(\%o193) } {a}_{0}\,{b}_{0}+\left(
    {a}_{1}\,{b}_{0}+{a}_{0}\,{b}_{1}\right) \,t+\left(
    {a}_{2}\,{b}_{0}+{a}_{1}\,{b}_{1}+{a}_{0}\,{b}_{2}\right)
  \,{t}^{2}+\\
  \left(
    {a}_{3}\,{b}_{0}+{a}_{2}\,{b}_{1}+{a}_{1}\,{b}_{2}+{a}_{0}\,{b}_{3}\right)
  \,{t}^{3}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o194) }
\sum_{n=0}^{\infty }\left( \sum_{k=0}^{n}{a}_{k}\,{b}_{n-k}\right) \,{t}^{n}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o195) }
\left( \sum_{k=0}^{0}{b}_{-k}\,{a}_{k}\right) +\left(
  \sum_{k=0}^{1}{b}_{1-k}\,{a}_{k}\right) \,t+\left(
  \sum_{k=0}^{2}{b}_{2-k}\,{a}_{k}\right) \,{t}^{2}+\\
\left( \sum_{k=0}^{3}{b}_{3-k}\,{a}_{k}\right) \,{t}^{3}+...
\end{math}\\
%%%%%%%%%%%%%%%
\\\\
The output \parbox{8ex}{\color{labelcolor}(\%o193) } is the product
$a(t)b(t)$, we can write it in a more compact form as done
in \parbox{8ex}{\color{labelcolor}(\%o194) }, recognizing the sum in brackets as the general term of a new sequence, so
$\mathcal{G}(a_n)\mathcal{G}(b_n) =\mathcal{G}\left(
  \sum_{k=0}^{n}{a}_{k}\,{b}_{n-k}\right)$.

\subsection{Translation of $\mathcal{G} $}

Let $\{a_n\}_{n\in\mathbb{N} }$ and $\{a_{n+1}\}_{n\in\mathbb{N} } $
be two sequences, $a(t)$ and $b(t)$ their formal power series,
reported in \parbox{8ex}{\color{labelcolor}(\%o79) }
and \parbox{8ex}{\color{labelcolor}(\%o80) } respectively. We study
how we can obtain $\mathcal{G}(a_{n+1}) $ from
$\mathcal{G} (a_n)$ with Maxima:\\

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i78)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
makeSequence(t,j,offset):=if is(offset >= 0) then sum
(j[i+offset]*t^i, i, 0, inf) else sum (j[i]*t^(i-offset), i, 0, inf)$
as:taylor(makeSequence(t,a,0), t, 0, 4);
bs:taylor(makeSequence(t,a,1), t, 0, 3);
(as-a[0])/t;
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o79) }
{a}_{0}+{a}_{1}\,t+{a}_{2}\,{t}^{2}+{a}_{3}\,{t}^{3}+{a}_{4}\,{t}^{4}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o80) }
{a}_{1}+{a}_{2}\,t+{a}_{3}\,{t}^{2}+{a}_{4}\,{t}^{3}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o81) }
{a}_{1}+{a}_{2}\,t+{a}_{3}\,{t}^{2}+{a}_{4}\,{t}^{3}+...
\end{math}
%%%%%%%%%%%%%%%
\\\\
To obtain $\mathcal{G}(a_{n+1})$ we subtract $a_0$ from $\mathcal{G}
(a_n)$, dividing the result by $t$, as reported
in \parbox{8ex}{\color{labelcolor}(\%o80) }, so:
\begin{equation*}
\mathcal{G}(a_{n+1})
= \frac{\mathcal{G} (a_n) - a_0}{t}
\end{equation*}

We can generalize, allowing arbitraty translation $s \geq 0$:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i249)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
load("simplify_sum");
sequence:makeSequence(t,a,0);
translated:makeSequence(t,a,s)$
(sequence - sum(a[i]*t^i,i,0,s-1))/t^s;
(taylor(sequence, t, 0, 55) - sum(a[i]*t^i,i,0,49))/t^50;
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o250) }
\sum_{i=0}^{\infty }{a}_{i}\,{t}^{i}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o252) }
\frac{\left( \sum_{i=0}^{\infty }{a}_{i}\,{t}^{i}\right) -\sum_{i=0}^{s-1}{a}_{i}\,{t}^{i}}{{t}^{s}}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o253) }
{a}_{50}+{a}_{51}\,t+{a}_{52}\,{t}^{2}+{a}_{53}\,{t}^{3}+{a}_{54}\,{t}^{4}+{a}_{55}\,{t}^{5}+...
\end{math}\\
%%%%%%%%%%%%%%%
where in the last line we've fixed $s = 50$. In general for an
arbitrary translation $s \geq 0$ holds:
\begin{equation*}
\mathcal{G}(a_{n+s}) =
\frac{\mathcal{G} (a_n) -\sum_{i=0}^{s-1}{a}_{i}\,{t}^{i}}{{t}^{s}}
\end{equation*}

If we have a negative translation $s < 0$, then we're in the following
context (in the following we use $a_{n-s}$, fixing the sing of $s >
0$):
\begin{displaymath}
  \begin{split}
    \mathcal{G} (a_n) &= a_0 + a_1 t + a_2 t^2 + \ldots + a_n t^n +
    \ldots \\
    \mathcal{G} (a_{n-s}) &= a_{-s} + a_{-s+1} t + \ldots + a_0 t^s +
    a_1 t^{s+1} + \ldots + a_n t^{n+s} + \ldots
  \end{split}
\end{displaymath}

With $a_k = 0$ for $k < 0$ since the sequence is defined only for $k
\in \mathbb{N} $. So we've:
\begin{displaymath}
  \mathcal{G} (a_{n-s}) =  a_0 t^s +
  a_1 t^{s+1} + \ldots + a_n t^{n+s} + \ldots = t^s \mathcal{G} (a_n)
\end{displaymath}

With Maxima:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i129)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
p:5$
cs:taylor(makeSequence(t,a,-p), t, 0, 10);
ds:taylor((t^p)*makeSequence(t,a,0), t, 0, 10);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o130) }
{a}_{0}\,{t}^{5}+{a}_{1}\,{t}^{6}+{a}_{2}\,{t}^{7}+{a}_{3}\,{t}^{8}+{a}_{4}\,{t}^{9}+{a}_{5}\,{t}^{10}+...
\end{math}\\
\begin{math}\displaystyle
  \parbox{8ex}{\color{labelcolor}(\%o131) }
  {a}_{0}\,{t}^{5}+{a}_{1}\,{t}^{6}+{a}_{2}\,{t}^{7}+{a}_{3}\,{t}^{8}+{a}_{4}\,{t}^{9}+{a}_{5}\,{t}^{10}+...
\end{math}
%%%%%%%%%%%%%%%


\subsection{Identity respect to product}

There exists a function $c(t)$ such that $a(t)c(t)=a(t)$, where $a(t)
= \mathcal{G} (a_n)$ and where $c(t) = \mathcal{G} (c_n)$? To answer
we apply the convolution property of $\mathcal{G} $:
\begin{displaymath}
  \mathcal{G} (a_n)\mathcal{G} (c_n) = \mathcal{G}\left(
    \sum_{k=0}^{n}{a}_{k}\,{c}_{n-k}\right)
\end{displaymath}
We impose the equality as desired $\mathcal{G} (a_n) = \mathcal{G}\left(
  \sum_{k=0}^{n}{a}_{k}\,{c}_{n-k}\right)$ which holds if the
sequences to which $\mathcal{G} $ is applied to are the same. Hence:
\begin{displaymath}
  a_n = \sum_{k=0}^{n}{a}_{k}\,{c}_{n-k} = a_0 c_n + a_1 c_{n-1} +
  \ldots + a_{n-1} c_1 + a_n c_0
\end{displaymath}
The above equality is true if and only if $c_0 = 1$ and $\forall
i\in\{1,\ldots,n\}:c_i = 0$. The sequence $\{c_n\}_{n\in \mathbb{N} }$
is something like $(1,0,0,0,0,\ldots)$ and its formal power series
$c(t) = \mathcal{G}(c_n) = 1 + 0t + 0t^2 + 0t^3 + \ldots $, hence we
rename $c(t) = 1(t)$.

\subsection{Inverse of a formal power series}


There exists a function $b(t)$ such that $a(t)b(t)=1(t)$, where $a(t)
= \mathcal{G} (a_n)$ and where $b(t) = \mathcal{G} (b_n)$? Lets study
the product $a(t)b(t)$:
\begin{displaymath}
  \begin{split}
    a(t)b(t) &= {a}_{0}\,{b}_{0}&+\left(
      {a}_{1}\,{b}_{0}+{a}_{0}\,{b}_{1}\right) \,t&+\left(
      {a}_{2}\,{b}_{0}+{a}_{1}\,{b}_{1}+{a}_{0}\,{b}_{2}\right)
    \,{t}^{2}&+ \ldots\\
    &= 1 &+ 0 &+ 0 &+ \ldots
  \end{split}
\end{displaymath}
The product $ a(t)b(t)$, reported
in \parbox{8ex}{\color{labelcolor}(\%o112) }, has to be equal to
$1(t)$, this allow to build a system, which we solve with Maxima,
obtaining the solutions reported
in \parbox{8ex}{\color{labelcolor}(\%o113) }:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i109)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
makeSequence(t,j):=sum (j[i]*t^i, i, 0, inf)$
makeSum(n):=sum (a[i]*b[n-i], i, 0, n)$
as:taylor(makeSequence(t,a), t, 0, 4);
bs:taylor(makeSequence(t,b), t, 0, 4);
prod:as*bs;
solve([makeSum(0)=1, makeSum(1)=0, makeSum(2)=0,
makeSum(3)=0, makeSum(4)=0],[b[0],b[1],b[2],b[3],b[4]]);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o110) }
{a}_{0}+{a}_{1}\,t+{a}_{2}\,{t}^{2}+{a}_{3}\,{t}^{3}+{a}_{4}\,{t}^{4}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o111) }
{b}_{0}+{b}_{1}\,t+{b}_{2}\,{t}^{2}+{b}_{3}\,{t}^{3}+{b}_{4}\,{t}^{4}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o112) }
{a}_{0}\,{b}_{0}+\left( {a}_{1}\,{b}_{0}+{a}_{0}\,{b}_{1}\right)
\,t+\left( {a}_{2}\,{b}_{0}+{a}_{1}\,{b}_{1}+{a}_{0}\,{b}_{2}\right)
\,{t}^{2}+\\
\left( {a}_{3}\,{b}_{0}+{a}_{2}\,{b}_{1}+{a}_{1}\,{b}_{2}+{a}_{0}\,{b}_{3}\right) \,{t}^{3}+\left( {a}_{4}\,{b}_{0}+{a}_{3}\,{b}_{1}+{a}_{2}\,{b}_{2}+{a}_{1}\,{b}_{3}+{a}_{0}\,{b}_{4}\right) \,{t}^{4}+...
\end{math}\\
\begin{math}\displaystyle
  \parbox{8ex}{\color{labelcolor}(\%o113) }
  [[{b}_{0}=\frac{1}{{a}_{0}},{b}_{1}=-\frac{{a}_{1}}{{a}_{0}^{2}},{b}_{2}=-\frac{{a}_{0}\,{a}_{2}-{a}_{1}^{2}}{{a}_{0}^{3}},{b}_{3}=-\frac{{a}_{0}^{2}\,{a}_{3}-2\,{a}_{0}\,{a}_{1}\,{a}_{2}+{a}_{1}^{3}}{{a}_{0}^{4}},\\
  {b}_{4}=-\frac{{a}_{0}^{3}\,{a}_{4}+{a}_{0}^{2}\,\left(
      -2\,{a}_{1}\,{a}_{3}-{a}_{2}^{2}\right)
    +3\,{a}_{0}\,{a}_{1}^{2}\,{a}_{2}-{a}_{1}^{4}}{{a}_{0}^{5}}]]
\end{math}\\
%%%%%%%%%%%%%%%
So the inverse of $a(t)$ is the function $a^{\langle -1\rangle}(t)=
b(t)$ such that $b(t)= \mathcal{G} (b_n )$, where
$\{b_n\}_{n\in\mathbb{N} } $ is such that $b_i$ is the $i$-th (zero
based indexing) solution reported
in \parbox{8ex}{\color{labelcolor}(\%o113) }. It is interesting to
observe that it is possible to find $a^{\langle -1\rangle}(t)$ if and
only if the first term of $\{a_n\}_{n\in\mathbb{N} } $ is such that
$a_0 \not = 0$.

\begin{exercise}
  Let $a(t) = 1-t$ be a formal power series such that $a(t) =
  \mathcal{G} (a_n)$. Find the inverse $a^{\langle -1\rangle}(t)$ and
  the ``inverse'' sequence $\{b_n\}_{n\in\mathbb{N} } $ such that
  $a^{\langle -1\rangle}(t) = \mathcal{G}(b_n) $.
\end{exercise}
\begin{proof}[Sol]
  We can find it immediately by setting $a(t)b(t)=1(t)$ and resolving
  respect to $b(t)$, obtaining $b(t) = \frac{1}{1-t} $ (to find the
  term $b_i$ of the sequence just expand $b(t)$ using Taylor and get
  the coefficients).

  To find the sequence $\{b_n\}_{n\in\mathbb{N} } $ such that
  $a^{\langle -1\rangle}(t) = \mathcal{G}(b_n) $, we use Maxima (where
  \texttt{\color{blue}sol} is the vector obtained in the previous
  Maxima output): in \parbox{8ex}{\color{labelcolor}(\%o91) } we
  report the coefficients of the sequence $\{b_n\}_{n\in\mathbb{N} } $
  using the solutions of the system reported
  in \parbox{8ex}{\color{labelcolor}(\%o113) } of the above paragraph,
  while in \parbox{8ex}{\color{labelcolor}(\%o93) } we expand the
  function $b(t) = \frac{1}{1-t} $ using Taylor, both methods returns
  the sequence $\{b_n\}_{n\in\mathbb{N} } = (1,1,1,1,1,\ldots)$.

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i90)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
as:[1,-1,0,0,0];
ev(sol[1],a[0]=as[1],a[1]=as[2],a[2]=as[3],a[3]=as[4],a[4]=as[5]);
b(t):=1/(1-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}(\%o90) }
[1,-1,0,0,0]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o91) }
[{b}_{0}=1,{b}_{1}=1,{b}_{2}=1,{b}_{3}=1,{b}_{4}=1]
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o92) }
\mathrm{b}\left( t\right) :=\frac{1}{1-t}
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o93) }
1+t+{t}^{2}+{t}^{3}+{t}^{4}+{t}^{5}+{t}^{6}+{t}^{7}+{t}^{8}+...
\end{math}\\
%%%%%%%%%%%%%%%
So the sequence $\{b_n\}_{n\in\mathbb{N} } =\{1_n\}_{n\in\mathbb{N} }
=(1,1,1,1,1,1,\ldots)$ is the ``inverse'' of $\{a_n\}_{n\in\mathbb{N}
} =(1,-1,0,0,0,0,\ldots)$, and we've found the following important
result:
\begin{equation}
  \label{eq:genfun-of-ones-sequence}
  b(t) = \mathcal{G} (1_n) =  \frac{1}{1-t}
\end{equation}
\end{proof}

\subsection{Derivation for $\mathcal{G} $}

Let $\{a_n\}_{n\in\mathbb{N} }$ and $\{n a_{n}\}_{n\in\mathbb{N} } $
be two sequences. We study how we can obtain $\mathcal{G}(n a_{n}) $,
reported in \parbox{8ex}{\color{labelcolor}(\%o212) } from
$\mathcal{G} (a_n)$, reported
in \parbox{8ex}{\color{labelcolor}(\%o211) }, with Maxima:

\noindent
%%%%%%%%%%%%%%%
%%% INPUT:
\begin{minipage}[t]{8ex}{\color{red}\bf
\begin{verbatim}
(%i207)
\end{verbatim}}
\end{minipage}
\begin{minipage}[t]{\textwidth}{\color{blue}
\begin{verbatim}
makeSum(n):=sum (a[i]*t^i, i, 0, n)$
makeDerSum(n):=sum (i*a[i]*t^i, i, 0, n)$
an(n):=taylor(makeSum(n),t,0,6)$
deran(n):=taylor(makeDerSum(n),t,0,6)$
an(6);
deran(6);
t*diff(an, t);
\end{verbatim}}
\end{minipage}
%%% OUTPUT:
\definecolor{labelcolor}{RGB}{100,0,0}
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o211) }
{a}_{0}+{a}_{1}\,t+{a}_{2}\,{t}^{2}+{a}_{3}\,{t}^{3}+{a}_{4}\,{t}^{4}+{a}_{5}\,{t}^{5}+{a}_{6}\,{t}^{6}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o212) }
{a}_{1}\,t+2\,{a}_{2}\,{t}^{2}+3\,{a}_{3}\,{t}^{3}+4\,{a}_{4}\,{t}^{4}+5\,{a}_{5}\,{t}^{5}+6\,{a}_{6}\,{t}^{6}+...
\end{math}\\
\begin{math}\displaystyle
\parbox{8ex}{\color{labelcolor}(\%o213) }
{a}_{1}\,t+2\,{a}_{2}\,{t}^{2}+3\,{a}_{3}\,{t}^{3}+4\,{a}_{4}\,{t}^{4}+5\,{a}_{5}\,{t}^{5}+6\,{a}_{6}\,{t}^{6}+...
\end{math}\\
%%%%%%%%%%%%%%%

Starting from $\mathcal{G} (a_n)$ we derive term-wise, obtaining $ a_1
+ 2a_2 t + 3a_3 t^2 + \ldots + a_n t^{n-1} + \ldots $, which in turn
we multiply by $t$, getting $\mathcal{G} (na_n)$. In compact form:
\begin{displaymath}
  \mathcal{G}(n a_n) = t \frac{\partial}{\partial
    t}\left( \mathcal{G} (a_n) \right)
\end{displaymath}

\subsection{Identity Principle}

Let $\{a_n\}_{n\in\mathbb{N} } $ and $\{b_n\}_{n\in\mathbb{N} } $ be
two sequences, the \emph{Identity Principle} states:
\begin{displaymath}
  \forall n \in \mathbb{N}: \left( a_n = b_n\right) \leftrightarrow
    \mathcal{G} (a_n) = \mathcal{G} (b_n)
\end{displaymath}

\begin{exercise}
  Suppose we forget the result shown in
  \autoref{eq:genfun-of-ones-sequence} about $\mathcal{G} (1_n) =
  \frac{1}{1-t} $, how can be used the \emph{Identity Principle} to
  prove that result?
\end{exercise}
\begin{proof}[Sol]
  In order to use the principle we've to find two sequences which are
  equal for all $n \in \mathbb{N} $. Since $\{a_n\}_{n\in\mathbb{N} }
  = (1,1,1,1,\ldots)$ we can build another sequence
  $\{a_{n+1}\}_{n\in\mathbb{N} } $ using $\{a_n\}_{n\in\mathbb{N} }
  $. But the index $n$ for the former and $n+1$ for the latter doesn't
  change the sequence, also $\{a_{n+1}\}_{n\in\mathbb{N} } =
  (1,1,1,1,\ldots)$, hence $\forall n\in \mathbb{N}: a_n =
  a_{n+1}$. By the principle $\mathcal{G} (a_n) = \mathcal{G}
  (a_{n+1})$ holds. We apply the translation property of $\mathcal{G}
  $:
  \begin{displaymath}
    \begin{split}
      \mathcal{G} (a_n) &= \mathcal{G} (a_{n+1}) = \frac{\mathcal{G}
        (a_n) - a_0}{t} \quad \text{by forward translation} \\
      \mathcal{G} (a_n) &= \frac{\mathcal{G}
        (a_n) -1}{t} \quad \text{where } a_0 = 1 \text{ by def of }
      \{a_n\}_{n\in\mathbb{N} }\\
      \mathcal{G} (a_n) &= \mathcal{G} (1_n) = \frac{1}{1-t}
    \end{split}
  \end{displaymath}
  What we now remember!
\end{proof}

The exercise above let us to generalize a little. Let
$\{a_n\}_{n\in\mathbb{N} } $ such that $a_n = c$. When the sequence is
known a priory as in this case (and in the exercise above), it is
useful to study the ratio between consecutive terms:
\begin{displaymath}
   \frac{a_{n+1}}{a_n} =  \frac{c}{c} \quad \rightarrow \quad a_{n+1}
   = a_n \quad \forall n \in \mathbb{N}
\end{displaymath}
By \emph{Identity Principle} follows:
\begin{displaymath}
  \begin{split}
    \mathcal{G} (a_n) &= \mathcal{G} (a_{n+1}) = \frac{\mathcal{G}
      (a_n) - a_0}{t} \quad \quad \text{where } a_0 = c \text{ by def
      of }
    \{a_n\}_{n\in\mathbb{N} } \\
    \mathcal{G} (a_n) &= \frac{\mathcal{G}
      (a_n) -c}{t} \\
    \mathcal{G} (a_n) &= c\mathcal{G} (1_n) = \frac{c}{1-t}
  \end{split}
\end{displaymath}

\subsection{Composition for $\mathcal{G} $}

Let $\{a_n\}_{n\in\mathbb{N} } $ and $\{b_n\}_{n\in\mathbb{N} } $ be
two sequences, we can compose their formal power series in the
following way:
\begin{displaymath}
  \begin{split}
    a(t) &= \sum_{k\geq 0}{a_k t^k} \quad b(t)= \mathcal{G} (b_n) \\
    \mathcal{G} (a_n) \circ \mathcal{G}(b_n) &= a(b(t)) =
    \sum_{k=0}^{\infty}{a_k b(t)^k}=
    \sum_{k=0}^{\infty}{a_k \mathcal{G} (b_n)^k}
  \end{split}
\end{displaymath}

\subsection{$\mathcal{G} ( \frac{1}{n} a_n) = \int{ \frac{\mathcal{G}
      (a_n) - a_0}{t}dt }$}

Let $b_n = \frac{1}{n} a_n$ be the generic term of a new sequence
$\{b_n\}_{n\in\mathbb{N} } $. It follows that $a_n = n b_n$, but it
isn't sufficient to apply the \emph{Identity Principle} because in
$n=0$ the term $b_0$ isn't defined. So we've to augment $a_n = n b_n +
a_0\delta_{n,0}$:
\begin{displaymath}
  \begin{split}
    a_n &= n b_n + a_0\delta_{n,0} \\
    &\downarrow \\
    \mathcal{G} (a_n) &= \mathcal{G} (n b_n) + \mathcal{G}
    (a_0\delta_{n,0})\\
    \mathcal{G} (a_n) &= t \frac{\partial}{\partial t}\left(
      \mathcal{G} ( b_n) \right) + a_0\mathcal{G} (\delta_{n,0})  \\
    \mathcal{G} (a_n) &= t \frac{\partial}{\partial t}\left(
      \mathcal{G} ( \frac{1}{n} a_n) \right) + a_0 \quad \text{by }
    \mathcal{G} (\delta_{n,0}) = 1\\
    \frac{\partial}{\partial t}\left( \mathcal{G} ( \frac{1}{n} a_n)
    \right) &= \frac{\mathcal{G} (a_n) - a_0}{t}\\
    \mathcal{G} ( \frac{1}{n} a_n) &=\int{ \frac{\mathcal{G} (a_n) -
        a_0}{t}dt}
  \end{split}
\end{displaymath}

\subsection{$\mathcal{G} ( \frac{1}{n+1} a_n) = \frac{1}{t} \int{
    \mathcal{G} (a_n)dt }$}

Let $g_n = a_{n-1}$, where $g_0 = 0$ (otherwise $a_{-1}$ hasn't
meaning), to have:
\begin{displaymath}
  \frac{1}{n+1} a_n = \frac{1}{n+1} g_{n+1}
\end{displaymath}
We apply the \emph{Identity Principle} directly because
we've just renamed the general term of the sequence:
\begin{displaymath}
  \begin{split}
    \frac{1}{n+1} a_n &= \frac{1}{n+1} g_{n+1} \\
    &\downarrow\\
    \mathcal{G} (\frac{1}{n+1} a_n) &= \mathcal{G} (\frac{1}{n+1}
    g_{n+1}) \\
    \mathcal{G} (\frac{1}{n+1} a_n) &= \frac{ \mathcal{G} (\frac{1}{n}
      g_n)-g_0}{t} \quad \text{ by translation of
    }\mathcal{G} \\
    \mathcal{G} (\frac{1}{n+1} a_n) &= \frac{1}{t} \mathcal{G}
    (\frac{1}{n} g_n)    \quad g_0 = 0\\
    \mathcal{G} (\frac{1}{n+1} a_n) &= \frac{1}{t} \int{
      \frac{\mathcal{G} (g_n) - g_0}{t}dt } \quad \text{by previous
      result}\\
    \mathcal{G} (\frac{1}{n+1} a_n) &= \frac{1}{t} \int{
      \frac{\mathcal{G} (a_{n-1})}{t}dt }
  \end{split}
\end{displaymath}
Recalling that $\mathcal{G} (a_{n-1}) = t \mathcal{G} (a_n)$, we have:
\begin{equation}
  \label{eq:n-plus-one-a-n-gen-fun}
  \mathcal{G} (\frac{1}{n+1} a_n) = \frac{1}{t} \int{ \mathcal{G}
    (a_{n})dt }
\end{equation}