\documentclass[reqno,11pt]{amsart}
\marginparwidth 0pt
\oddsidemargin 0 in
\evensidemargin 0 in
\marginparsep 0pt
\topmargin -0.3 in
\textwidth 6in
\textheight 9 in
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}
\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
#1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\slanttheorems
\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}[theorem]{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\theorembodyfont{\slshape}
\newtheorem{ncor}[theorem]{Corollary}
\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\newcommand\U{{\mathcal{U}}}
\newcommand\E{{\mathcal{E}}}
\newcommand\T{{\mathcal{T}}}
\renewcommand\P{{\mathcal{P}}}
\renewcommand\a{{\bold{a}}}
\newcommand\p{{\bold{p}}}
\newcommand\mcirc{{\bigcirc}}
\newcommand\dilog{\operatorname{dilog}}
\newcommand\C{{\mathcal C}}
\newcommand{\stwo}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newcommand{\sone}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\def\cauchy{\frac{1}{2i\pi}}
\def\H{{\mathcal{H}}}
\def\B{{\mathcal{B}}}
\newcommand\bl{\operatorname{L}}
\RequirePackage{theorem}
\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}
% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}
\newcommand{\ackno}{\section*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}
\renewcommand{\thefootnote}{}
\begin{document}
\author{Alois Panholzer and Helmut Prodinger}
\title[A more precise analysis of an algorithm to generate
binary trees]
{Towards a more precise analysis of an algorithm to generate
binary trees : A tutorial}\footnote{This research was supported by
the Austrian Research Society (FWF) under the project number \textup{P12599-MAT}}
\date{\today}
\begin{abstract}
For the analysis of an algorithm to generate binary trees
\cite{XiTaUs97}, the behaviour of a certain sequence of numbers
is essential. In the original paper, it was expressed by a recursion.
Here, we show how to solve this (and similar) recursions, both,
explicitly and asymptotically. Some additional information about
useful mathematical software is also provided.
\end{abstract}
\maketitle
%Filename: C:$\backslash$texfiles$\backslash$chinese.tex
\section{Introduction}
In the analysis of an algorithm to generate binary trees the authors of
\cite{XiTaUs97} came up with a double sequence $g_{n,k}$ and gave a
recursion for it (Theorem 9, with notation changed). The sequence
$g_{n,0}$ was of particular interest.
Since there was no analysis provided we think that it is appropriate
to explain here how such recursions can be treated properly.
Especially we want to discuss generating functions, explicit forms,
asymptotic expansions, and convenient Computer software.
It is a little bit nicer to explain things for a slightly modified recursion
that seems to be more natural. However, the original one can be treated
in the same way, as we will also demonstrate.
Here is the recursion:
\begin{equation}
g_{n,k}=g_{n-1,k-1}+2g_{n-1,k}+g_{n-1,k+1}+1\qquad\text{for }0\le k\le n
\end{equation}
with the assumption that all values $g_{n,k}$
outside the range $0\le k\le n $ are zero.
\section{Generating functions}
As in Knuth \cite[page 537]{Knuth68} we set up the generating function
\begin{equation*}
G(x,z)=\sum_{0\le k\le n }g_{n,k}x^kz^n.
\end{equation*}
Summing up the recursion (multiplied by $x^kz^n$) we find
\begin{equation*}
G(x,z)=zxG(x,z)+2zG(x,z)+\frac{z}{x}\big(G(x,z)-g(z)\big)
+\sum_{0\le k\le n }x^kz^n,
\end{equation*}
with $g(z)=G(0,z)$. Note that
\begin{equation*}
\sum_{0\le k\le n }x^kz^n=
\sum_{k\ge0}\sum_{j\ge0}x^kz^{k+j}=\frac{1}{1-z}
\sum_{k\ge0}(zx)^k=\frac{1}{(1-z)(1-zx)}.
\end{equation*}
Hence
\begin{equation*}
G(x,z)=\frac{zg(z)-\frac{x}{(1-z)(1-zx)}}
{zx^2+(2z-1)x+z}
\end{equation*}
Now note that
\begin{equation*}
zx^2+(2z-1)x+z=z\big(1-xr_1(z)\big)\big(1-xr_2(z)\big)
\end{equation*}
with
\begin{equation*}
r_{1,2}(z)=-1+\frac{1\pm\sqrt{1-4z}}{2z}.
\end{equation*}
Now, again as Knuth, we argue that $G(x,z)$ has a power series expansion
in $z$ and $x$. Since the denominator vanishes for
$x=r_2(z)$, the numerator should also vanish, which means
\begin{equation*}
zg(z)=\frac{r_2(z)}{(1-z)(1-zr_2(z))},
\end{equation*}
which leads already to the solution
\begin{equation}\label{g_loes}
g(z)=\frac{r_2(z)}{z(1-z)(1-zr_2(z))}.
\end{equation}
\section{Explicit expressions}
As it is perhaps not too surprising, there are some close connections with
{\it Catalan numbers}, since
\begin{equation*}
B(z)=\frac{1-\sqrt{1-4z}}{2z}=\sum_{n\ge0}\frac{1}{n+1}\binom{2n}{n}z^n.
\end{equation*}
Note that
\begin{equation*}
r_2(z)=-1+B(z)=zB^2(z).
\end{equation*}
There is a convenient method to pull out coefficients, using
(formal) residue calculus, compare e.~g. \cite{BrKnRi72}: On sets
$z=u/(1+u)^2$, then
\begin{equation*}
g(z)=\left[
\frac{4}{3}\frac{1}{1+2u}-\frac{1}{3}\frac{(1+2u)(1-u)}{1-u^3}
\right](1+u)^6.
\end{equation*}
Now
\begin{align*}
[z^n]g(z)&=\frac{1}{2\pi i}\oint\frac{dz}{z^{n+1}}g(z)\\
&=\frac{1}{2\pi i}\oint\frac{du(1-u)(1+u)^{2n+2}}{(1+u)^3u^{n+1}}g\big(z(u)\big)\\
&=[u^n]{(1-u)(1+u)^{2n-1}}g\big(z(u)\big)\\
&=[u^n]{(1-u)(1+u)^{2n-1}}\left[
\frac{4}{3}\frac{1}{1+2u}-\frac{1}{3}\frac{(1+2u)(1-u)}{1-u^3}
\right](1+u)^6\\
&=[u^n]{(1+u)^{2n+5}}\left[
\frac{4}{3}\frac{1-u}{1+2u}-\frac{1}{3}\frac{(1+2u)(1-u)^2}{1-u^3}
\right]\,.
\end{align*}
Note that
\begin{equation*}
[u^{n-k}](1-u)(1+u)^{2n+5}=2\frac{k+3}{n+k+6}\binom{2n+5}{n-k}
\end{equation*}
and $(1+2u)(1-u)^2=1-3u^2+2u^3$ and further
\begin{align*}
[u^{n-3k}]&(1-3u^2+2u^3)(1+u)^{2n+5}\\&=
\frac {2 (3{n}^{2}-54n{k}^{2}-153nk-87n+54{k}^{3}+54{k}^{2}-177k-168)}
{\left (n+8+3k\right )\left (n+7+3k\right )\left (n+6+3k\right )}
\binom{2n+5}{n-3k}.
\end{align*}
Hence
\begin{align} \begin{split}
[z^n]g(z)&=\frac{8}{3}\sum_{0\le k\le n}(-2)^k
\frac{k+3}{n+k+6}\binom{2n+5}{n-k}\\&+
\frac{2}{3}\sum_{0\le 3k\le n}
{\frac {3{n}^{2}-54n{k}^{2}-153nk-87n+54{k}^{3}+54{k}^{2}-177k-168}
{\left (n+8+3k\right )\left (n+7+3k\right )\left (
n+6+3k\right )}}\binom{2n+5}{n-3k} \, .
\end{split}\end{align}
This is admittedly not too nice, but it has only one (level of) summation, and
we cannot hope to do better than that.
Another approach would be based on the formula
\begin{equation*}
g(z)=\frac{1}{z^2(1-z)}\sum_{k\ge1}\big(zB(z)\big)^{2k},
\end{equation*}
but that would lead to a double summation of the coefficients.
\section{Asymptotics}
The explicit form (\ref{g_loes})
suggests to expand $g(z)$ around its (dominant) singularity
$z=\frac14$, viz.
\begin{equation*}
g(z)\sim \frac{64}{9}-\frac{512}{27}\sqrt{1-4z},
\end{equation*}
with more terms available.
Now singularity analysis of generating functions \cite{FlOd90} tells us
that
\begin{equation*}
g_{n,0}=[z^n]g(z)\sim \frac{256}{27\sqrt{\pi}}\,4^n\,n^{-3/2}.
\end{equation*}
\section{A recursion}
With Zeilberger's algorithm \cite{PeWiZe96} we can first {\it guess \/}
a linear recursion with polynomial coefficients for the values
$g_{n} := g_{n,0}$, which can be {\it proved\/} afterwards, just by looking at
the corresponding linear differential equation with polynomial
coefficients for the generating function $g(z)$.
In this manner we get for $g_{n}$ the recursion
\begin{equation*}
( n+6) g_{n+3} + (\tfrac{9}{2} n-21) g_{n+2}
+ (\tfrac{3}{2} n+6) g_{n+1}
+( 2n+9) g_{n}
= 0
\end{equation*}
with initial values $g_{0}=1$, $g_{1}=3$ and $g_{2}=9$.
The corresponding differential equation for $g(z)$ can be written as
\begin{equation*}
\frac{1}{2} z (z-1)(z+2)(4z-1) g'(z) +
\frac{1}{2} (18z^{3}+9z^{2}-24z+6) g(z) -3 = 0
\end{equation*}
with initial condition $g(0) = 1$. Now this differential equation
can be solved (or, we might just check that its solution is
(\ref{g_loes}))
and therefore the validity of the above recursion is easily verified.
A very useful tool in this context is the program {\sc Gfun} \cite{SaZi94}.
It would also guess the above recursion, based on the first few values. Or, it would
transform the explicit form of $g(z)$ into an algebraic equation for it, and this
equation into an equivalent differential equation, from which the recursion with
polynomial coefficients would be available.
\section{The original recursion}
The original recursion from \cite{XiTaUs97} that we want to treat is
\begin{equation}
\widetilde{g}_{n,k}=\widetilde{g}_{n-1,k-1}+2\widetilde{g}_{n-1,k}+
\widetilde{g}_{n-1,k+1}+1\quad\text{for }
0\le k < n \; \text{and} \; n \ge 2
\end{equation}
with the assumption that all other values $\widetilde{g}_{n,k}$ are zero.
When we introduce the bivariate generating function
\begin{equation*}
\widetilde{G}(x,z)=\sum_{0\le k\le n }\widetilde{g}_{n,k}x^kz^n \, ,
\end{equation*}
this recursion leads by multiplication with $z^{n}x^{k}$ and
summing up to the equation
\begin{equation*}
G(x,z)=zxG(x,z)+2zG(x,z)+\frac{z}{x}\big(G(x,z)-g(z)\big)
+\sum_{\stackrel{0\le k < n,}{n \ge 2}}x^kz^n,
\end{equation*}
with $\widetilde{g}(z)=\widetilde{G}(0,z)$. Of course we have
\begin{equation*}
\sum_{\stackrel{0\le k < n,}{n \ge 2} }x^kz^n=
\sum_{0 \le k