\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{tikz} \usetikzlibrary{decorations.pathreplacing} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \newenvironment{dedication} {\vspace{6ex}\begin{quotation}\begin{center}\begin{em}} {\par\end{em}\end{center}\end{quotation}} \allowdisplaybreaks \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Summations in Bernoulli's Triangles via Generating Functions\\ \vskip .11in } \vskip 1cm \large Kamilla Oliver\\ 9 Stellenberg Road\\ 7130 Somerset West\\ South Africa \\ \href{mailto:olikamilla@gmail.com}{\tt olikamilla@gmail.com} \\ \ \\ \large Helmut Prodinger\\ Department of Mathematical Sciences\\ Stellenbosch University\\ 7602 Stellenbosch\\ South Africa\\ \href{mailto:hproding@sun.ac.za}{\tt hproding@sun.ac.za} \\ \end{center} \begin{dedication} For Philippe Flajolet (1948--2011), the master and advocate of generating functions. \end{dedication} \vskip .2 in \begin{abstract} We revisit sums along straight lines of indices in Bernoulli triangles, and emphasize the use of generating functions as the appropriate tool. This leads to more direct and extended results, compared with a recent paper in this journal. \end{abstract} \section{Introduction} Let \begin{equation*} B^{[1]}_{n,k}=\binom nk\quad\text{and}\quad B^{[m+1]}_{n,k}=\sum_{0\le j \le k}B^{[m]}_{n,j},\quad m\ge1. \end{equation*} A recent study \cite{NePr16} refers to these numbers as the $m$-th Bernoulli triangle. In particular, sums in them, along certain straight lines, are studied. We revisit these problems and treat them with generating functions because experience showed as that such an approach is well suited for the problems at hand. It leads to quicker and cleaner proofs and also to extended results. We hope that the readers might find our treatment interesting. As a general reference to the methods that we use, we would like to mention the book \emph{Analytic Combinatorics} \cite{FlSe09}. We would also like to give a pointer to the \textsc{gfun} package by Salvy and Zimmermann, as available by now in Maple~\cite{SaZi94}. Our first observation is that the iterated sums can be reduced to a single summation: \begin{gather*} B^{[2]}_{n,k}=\sum_{0\le h \le k}\binom nh,\\ B^{[3]}_{n,k}=\sum_{0\le h \le j \le k}\binom nh=\sum_{0\le h \le k}\binom nh(k+1-h),\\ B^{[4]}_{n,k}=\sum_{0\le h \le j\le k}\binom nh(j+1-h)=\sum_{0\le h \le k}\binom nh\binom{k+2-h}{2}, \end{gather*} and in general, by induction, \begin{equation*} B^{[m]}_{n,k}=\sum_{0\le h \le k}\binom nh\binom{k+m-2-h}{m-2}. \end{equation*} Let \begin{equation*} F_m(z,y):=\sum_{0\le k \le n}B^{[m]}_{n,k}z^ny^k. \end{equation*} Then \begin{equation*} F_1(z,y):=\sum_{0\le k \le n}\binom nkz^ny^k=\sum_{0 \le n}(1+y)^nz^n=\frac{1}{1-z(1+y)}. \end{equation*} It is even beneficial to introduce a \emph{trivariate} generating function: \begin{align*} H(z,y,w)&:=\sum_{m\ge1}F_m(z,y)w^{m-1}\\ &=F_1(z,y)+\sum_{m\ge2}w^{m-1}\sum_{0\le k \le n}\sum_{0\le h \le k}\binom nh\binom{k+m-2-h}{m-2}z^ny^k\\ &=\frac{1}{1-z(1+y)}+w\sum_{m\ge0}w^{m}\sum_{0\le h \le k\le n}\binom nh\binom{k+m-h}{m}z^ny^k\\ &=\frac{1}{1-z(1+y)}+w\sum_{0\le h \le k\le n}(1-w)^{h-k-1}\binom nhz^ny^k\\ &=\frac{1}{1-z(1+y)}+\frac{w}{y-1+w}\sum_{0\le h \le n} \bigg[(1-w)^{h-1-n}y^{n+1}-y^h\bigg]\binom nhz^n\\ &=\frac{1}{1-z(1+y)}+\frac{w}{y-1+w}\sum_{0 \le n} (1-w)^{-1-n}y^{n+1}(2-w)^nz^n\\ &\hspace*{4cm}-\frac{w}{y-1+w}\sum_{0 \le n} (1+y)^nz^n\\ &=\frac{1}{1-z(1+y)}+\frac{w}{y-1+w}\frac{y}{1-w}\frac{1-w}{1-w-yz(2-w)}\\ &\hspace*{4cm}-\frac{w}{y-1+w}\frac{1}{1-z(1+y)}\\ &=\frac1{1-z(1+y)}\frac{1}{1-w\frac{1-zy}{1-2zy}}. \end{align*} Hence \begin{equation*} F_m(z,y)=[w^{m-1}]\frac1{1-z(1+y)}\frac{1}{1-w\frac{1-zy}{1-2zy}}= \frac1{1-z(1+y)}\frac{(1-zy)^{m-1}}{(1-2zy)^{m-1}}. \end{equation*} We want to point out at that stage how to extract the \emph{diagonal} from a bivariate generating function $F(z,y)$. The procedure was first observed by Hautus and Klarner \cite{HaKl71} but is by now almost a standard tool in combinatorial analysis. \begin{equation*} \sum_{n\ge0}F(n,n)z^n=\frac{1}{2\pi i}\int_{\mathcal{C}}\frac{dt}{t}F\bigl(\frac zt,t\bigr), \end{equation*} where the curve $\mathcal{C}$ winds around the origin exactly once. This integral can be evaluated as a sum over the residues of $F(\frac zt,t)\frac 1t$, over the ``small'' solutions $t=s(z)$, i.e., those that satisfy $s(z)\to0$ for $z\to0$ (these poles stay inside the curve, if it is made sufficiently small). We will apply this principle for trivariate generating functions, where the third variable $w$ is treated as a parameter. \section{A summation} The following sum was of interest for Neiter and Proag \cite{NePr16} \begin{equation*} \sum_{j\ge0}B^{[m]}_{n-j,k-2j}. \end{equation*} We can be careless about the range of summation, since only terms of the form $0\le k-2j\le n-j$ contribute; others being automatically equal to zero. The extra factor $\frac{1}{1-zy^2}$ generates this summation, applied to the generating function $F_m(z,y)$: \begin{equation*} \frac{1}{1-zy^2}\frac{(1-zy)^{m-1}}{(1-2zy)^{m-1}(1-z(1+y))}. \end{equation*} Since the interest is/was only for $n=k$, we extract the diagonal from this generating function, or even from the trivariate generating function \begin{equation*} \frac{1}{1-zy^2}\sum_{m\ge1}F_m(z,y)w^{m-1}= \frac{1}{1-zy^2}\frac1{1-z(1+y)}\frac{1}{1-\frac{w(1-zy)}{1-2zy}}. \end{equation*} As mentioned before, the diagonal is the contour integral \begin{multline*} \frac1{2\pi i}\oint \frac {dt}t\frac{1}{1-zt}\frac1{1-z/t(1+t)}\frac{1-2z}{1-2z-w(1-z)}\\=\frac1{2\pi i}\oint dt\frac{1}{1-zt}\frac1{t-z(1+t)}\frac{1-2z}{1-2z-w(1-z)}. \end{multline*} There are two poles: $t=1/z$ and $t=z/(1-z)$. Only the second one is ``small'' and we compute the residue: \begin{align*} \text{Res}_{t=z/(1-z)}&\bigg\{\frac{1}{1-zt}\frac1{t-z(1+t)}\frac{1-2z}{1-2z-w(1-z)}\bigg\}\\ &=\frac{1}{1-z^2/(1-z)}\frac1{1-z}\frac{1-2z}{1-2z-w(1-z)}\\ &=\frac{1}{1-z-z^2}\frac{1-2z}{1-2z-w(1-z)}\\ &=\frac{1}{1-z-z^2}\sum_{m\ge0}w^m\frac{(1-z)^m}{(1-2z)^m}. \end{align*} We note for further reference that \begin{equation*} \frac{1}{1-z-z^2}=\sum_{n\ge0}F_{n+1}z^n \end{equation*} is the generating function of the Fibonacci numbers \cite{GrKnPa94}. Let us start with the simple instance $m=1$ and extract the coefficient of $w^{m-1}$: \begin{equation*} \frac{1}{1-z-z^2}, \end{equation*} so that \begin{equation*} \sum_{j\ge0}\binom{n-j}{n-2j}=\sum_{0\le j \le n/2}\binom{n-j}{j}=F_{n+1}, \end{equation*} which is classical. Now we move to the instance $m=2$ and extract the coefficient of $w^{m-1}$: \begin{equation*} \frac{1}{1-z-z^2}\frac{1-z}{1-2z}=\frac{2}{1-2z}-\frac{1+z}{1-z-z^2}. \end{equation*} Reading off the coefficient of $z^n$ here leads to \begin{equation*} 2^{n+1}-F_{n+1}-F_{n}=2^{n+1}-F_{n+2}, \end{equation*} which is the evaluation of \begin{equation*} \sum_{j\ge0}B^{[2]}_{n-j,n-2j}. \end{equation*} By computing the partial fraction decomposition, the next few instances are \begin{gather*} (n-1)2^n+F_{n+3},\qquad(m=3)\\ \Big(\frac{n^2}{4}+\frac{n}{4}+4\Big)2^n-F_{n+4},\qquad(m=4)\\ \Big(\frac{n^3}{24}+\frac{n^2}{4}+\frac{53n}{24}-4\Big)2^n+F_{n+5},\qquad(m=5) \end{gather*} and we wonder if we can say anything in general. We can indeed apply the principle of partial fraction decomposition directly to \begin{multline*} \frac{1}{1-z-z^2}\frac{1-2z}{1-2z-w(1-z)}\\ =\frac {w ( 2-w ) }{ ( 1+w-{w}^{2}) ( 1-w-z(2-w) ) } +\frac {1-zw}{ (1-z-{z}^{2})(1+w- {w}^{2}) }. \end{multline*} The second term is easier: \begin{align*} [z^nw^{m-1}]&\frac {1-zw}{ (1-z-{z}^{2})(1+w- {w}^{2}) }=[w^{m-1}]\frac{F_{n+1}-wF_n}{1+w- {w}^{2}}\\ &=(-1)^{m-1}[w^{m-1}]\frac{F_{n+1}+wF_n}{1-w- {w}^{2}}\\ &=(-1)^{m-1}(F_{n+1}F_{m}+F_nF_{m-1})=(-1)^{m-1}F_{n+m}. \end{align*} This is the term that we observed earlier, from the first few instances. The first term could be expanded to any number of terms, but it does not seem that a nice closed formula comes out. The shape is \begin{equation*} \sum_{m\ge1}\frac{\textsf{polynomial in $z$ of degree $m-1$}}{(1-2z)^m}w^m. \end{equation*} Calling the polynomials in the numerator $u_m=u_m(z)$, Maple's \textsc{gfun} command computes the following recursion: \begin{equation*} u _{m+3 } -zu _{m+2 } - ( 2z-1 ) ( 3z-2 ) u_ { m+1 } - ( z-1) ( 2z-1 ) ^{2}u_ { m } =0, \end{equation*} with initial conditions $u_0 = 0$, $u_1 = 2$, $u_2 = 4z-1$. \section{A more general summation} Let $c\ge1$ be an integer. We are, as our predecessors, interested in \begin{equation*} \sum_{j\ge0}B^{[m]}_{n-cj,k-(c+1)j}, \end{equation*} especially for $k=n$. Since the instance $c=1$ was discussed at length in the previous section, we can be brief here. The trivariate generating function of interest is now \begin{equation*} \frac{1}{1-z^cy^{c+1}}\frac1{1-z(1+y)}\frac{1}{1-\frac{w(1-zy)}{1-2zy}}. \end{equation*} Extracting the diagonal leads to the computation of the residue(s) of \begin{equation*} \frac{1}{1-z^ct}\frac1{t-z(1+t)}\frac{1-2z}{1-2z-w(1-z)}. \end{equation*} \begin{align*} \text{Res}_{t=z/(1-z)}&\bigg\{\frac{1}{1-z^ct}\frac1{t-z(1+t)}\frac{1-2z}{1-2z-w(1-z)}\bigg\}\\ &=\frac{1}{1-z^{c+1}/(1-z)}\frac1{1-z}\frac{1-2z}{1-2z-w(1-z)}\\ &=\frac{1}{1-z-z^{c+1}}\frac{1-2z}{1-2z-w(1-z)}\\ &=\frac{1}{1-z-z^{c+1}}\sum_{m\ge0}w^m\frac{(1-z)^m}{(1-2z)^m}. \end{align*} The first factor generates some generalized Fibonacci number. We keep the notation of Neiter and Proag \cite{NePr16}: \begin{equation*} \frac{z^c}{1-z-z^{c+1}}=\sum_{n\ge0}\lambda_n(c)z^n. \end{equation*} For $m=1$, the coefficient of $w^{m-1}$ leads to \begin{equation*} \frac{1}{1-z-z^{c+1}}=\sum_{n\ge0}\lambda_{n+c}(c)z^n, \end{equation*} and thus we have the first summation \begin{equation*} \sum_{j\ge0}B^{[1]}_{n-cj,n-(c+1)j}=\lambda_{n+c}(c). \end{equation*} For $m=2$, the coefficient of $w^{m-1}$ leads to \begin{equation*} \frac{1}{1-z-z^{c+1}}\frac{1-z}{1-2z}=\frac{2^c}{2^c-1}\frac1{1-2z}-\frac{1}{2^c-1}\frac{1+\sum_{j=1}^c2^{j-1}z^j}{1-z-z^{c+1}} \end{equation*} and the coefficient of $z^n$ is given by \begin{equation*} \frac{2^c}{2^c-1}2^n-\frac{1}{2^c-1}\Big(\lambda_{n+c}(c)+\sum_{j=1}^c2^{j-1}\lambda_{n+c-j}(c)\Big), \end{equation*} which is the summation for \begin{equation*} \sum_{j\ge0}B^{[2]}_{n-cj,n-(c+1)j}. \end{equation*} We stop here since further instances become a bit clumsy. \section{Another summation} The next type of summation that we will treat with generating functions is \begin{equation*} \sum_{0\le j\le n/2}B^{[m]}_{n-j,j}. \end{equation*} In this case one has to be careful not to include unwanted terms in the summation. Let us start with $m=1$: \begin{equation*} \sum_{0\le j\le n/2}\binom{n-j}{j}=\sum_{0\le j\le n}\binom{n-j}{j}. \end{equation*} We consider (again) the generating function \begin{equation*} \sum_{0\le j\le n}z^n\binom{n-j}{j}=\sum_{j,k\ge0}z^kz^j\binom{k}{j}=\frac{1}{1-z(1+z)}, \end{equation*} whence we get $F_{n+1}$ for the summation. Now let us move to $m=2$. \begin{align*} \sum_{0\le j\le n/2}&B^{[2]}_{n-j,j}=\sum_{0\le h\le j\le n/2}\binom{n-j}{h}\\ &=\sum_{0\le h\le j\le n}\binom{n-j}{h}-\sum_{n/2< j\le n}\sum_{h=0}^j\binom{n-j}{h}\\ &=\sum_{0\le h\le j\le n}\binom{n-j}{h}-\sum_{n/2< j\le n}2^{n-j} =\sum_{0\le h\le j\le n}\binom{n-j}{h}-2^{\lfloor(n+1)/2\rfloor}+1. \end{align*} The generating function related to the first term is \begin{align*} \sum_{n\ge0}z^n\sum_{0 \le h \le j \le n}\binom{n-j}{h} &=\sum_{n\ge0}z^n\sum_{0 \le h \le n}\binom{n+1-h}{h+1} =\sum_{h\ge0}z^h\sum_{n\ge h}z^{n-h}\binom{n+1-h}{h+1}\\ &=\sum_{h\ge0}z^h\sum_{k\ge0}z^{k}\binom{k+1}{h+1} =\sum_{h\ge0}z^h\frac{z^{h}}{(1-z)^{h+2}}\\ &=\frac1{(1-z)^{2}}\frac1{1-\frac{z^2}{1-z}}=\frac1{1-z}\frac1{1-z-z^2}=\frac{z+2}{1-z-z^2}-\frac1{1-z}. \end{align*} This leads to the evaluation \begin{equation*} F_{n}+2F_{n+1}-1-2^{\lfloor(n+1)/2\rfloor}+1= F_{n+3}-2^{\lfloor(n+1)/2\rfloor}. \end{equation*} In the same style one can also treat the higher instances $m=3,4,\dots$. However, we would like to offer a tool that is very useful: \textsc{gfun}, implemented in Maple, and in particular its guessing abilities. In this way, one can get results very quickly, although formal proofs would still be required. This leads for $m=2$ to \begin{equation*} \frac{z+2}{1-z-z^2}-\frac{1+2z}{1-2z^2}, \end{equation*} and for $m=3$ to \begin{equation*} \frac{3z+5}{1-z-z^2}-\frac12\frac{1+2z}{(1-2z^2)^2}-\frac12\frac{7+12z}{(1-2z^2)^2}, \end{equation*} with result \begin{equation*} F_{n+5}-\begin{cases}2^{k-1}(k+8),& \text{for } n=2k;\\ 2^{k}(k+7),& \text{for } n=2k+1. \end{cases} \end{equation*} The reader can create further examples herself. \begin{thebibliography}{1} \bibitem{FlSe09} P.~Flajolet and R.~Sedgewick, {\em Analytic Combinatorics}, Cambridge University Press, 2009. \bibitem{GrKnPa94} R.~L. Graham, D.~E. Knuth, and O.~Patashnik, {\em Concrete Mathematics}, 2nd edition, Addison-Wesley, 1994. \bibitem{HaKl71} M. L. J. Hautus and D. A. Klarner, The diagonal of a double power series, {\em Duke Math. J.} {\bf 38} (1971), 229--235. \bibitem{NePr16} D.~Neiter and A.~Proag, Links between sums over paths in {B}ernoulli's triangles and {F}ibonacci numbers, {\em J. Integer Sequences} {\bf 19} (2016), \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Proag/proag3.html}{Article 16.8.3}. \bibitem{SaZi94} Bruno Salvy and Paul Zimmermann, \textsc{Gfun}: a {M}aple package for the manipulation of generating and holonomic functions in one variable, {\em ACM Trans. Math. Software} {\bf 20} (1994), 163--177. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19, 11B39. \noindent \emph{Keywords: } Bernoulli triangle, generating function, diagonal of a double power series. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000108}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 12 2016. Revised version received December 25 2016. Published in {\it Journal of Integer Sequences}, December 26 2016. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .