Summations in Bernoulli’s Triangles via Generating Functions

Kamilla Oliver 9 Stellenberg Road 7130 Somerset West South Africa

                 olikamilla@gmail.com

Helmut Prodinger Department of Mathematical Sciences Stellenbosch University 7602 Stellenbosch South Africa

                  hproding@sun.ac.za

For Philippe Flajolet (1948–2011), the master and advocate of generating functions.

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.

1 Introduction

Let

B_{n,k}^{[1]} = \binom{n}{k} and B_{n,k}^{[m+1]} = ∑_{0≤j≤k} B_{n,j}^{[m]}, m ≥ 1.

A recent study [4] 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 Analytic Combinatorics [1]. We would also like to give a pointer to the gfun package by Salvy and Zimmermann, as available by now in Maple [5].

Our first observation is that the iterated sums can be reduced to a single summation:

B_{n,k}^{[2]} = ∑_{0≤h≤k} \binom{n}{h},

B_{n,k}^{[3]} = ∑_{0≤h≤j≤k} \binom{n}{h} = ∑_{0≤h≤k} \binom{n}{h}(k + 1 − h),

B_{n,k}^{[4]} = ∑_{0≤h≤j≤k} \binom{n}{h}(j + 1 − h) = ∑_{0≤h≤k} \binom{n}{h}\binom{k + 2 − h}{2},

and in general, by induction,

B_{n,k}^{[m]} = ∑_{0≤h≤k} \binom{n}{h}\binom{k + m − 2 − h}{m − 2}.

Let

F_{m}(z, y) := ∑_{0≤k≤n} B_{n,k}^{[m]}z^{n}y^{k}.

Then

F_{1}(z, y) := ∑_{0≤k≤n} \binom{n}{k}z^{n}y^{k} = ∑_{0≤n}(1 + y)^{n}z^{n} = \frac{1}{1 − z(1 + y)}.

It is even beneficial to introduce a trivariate generating function:

H(z, y, w) := ∑_{m≥1} F_{m}(z, y)w^{m−1}

= F_{1}(z, y) + ∑_{m≥2} w^{m−1} ∑_{0≤k≤n} ∑_{0≤h≤k} \binom{n}{h}\binom{k + m − 2 − h}{m − 2}z^{n}y^{k}

= \frac{1}{1 − z(1 + y)} + w ∑_{m≥0} w^{m} ∑_{0≤h≤k≤n} \binom{n}{h}\binom{k + m − h}{m}z^{n}y^{k}

= \frac{1}{1 − z(1 + y)} + w ∑_{0≤h≤k≤n}(1 − w)^{h−k−1}\binom{n}{h}z^{n}y^{k}

= \frac{1}{1 − z(1 + y)} + \frac{w}{y − 1 + w} ∑_{0≤h≤n} [(1 − w)^{h−1−n}y^{n+1} − y^{h}]\binom{n}{h}z^{n}

= \frac{1}{1 − z(1 + y)} + \frac{w}{y − 1 + w} ∑_{0≤n}(1 − w)^{−1−n}y^{n+1}(2 − w)^{n}z^{n}

− \frac{w}{y − 1 + w} ∑_{0≤n}(1 + y)^{n}z^{n}

= \frac{1}{1 − z(1 + y)} + \frac{w}{y − 1 + w} \frac{y}{1 − w} \frac{1 − w}{1 − w − yz(2 − w)}

− \frac{w}{y − 1 + w} \frac{1}{1 − z(1 + y)}

= \frac{1}{1 − z(1 + y)} \frac{1}{1 − w\frac{1−zy}{1−2zy}} .

Hence

F_{m}(z, y) = [w^{m−1}]\frac{1}{1 − z(1 + y)} \frac{1}{1 − w\frac{1−zy}{1−2zy}} = \frac{1}{1 − z(1 + y)} \frac{(1 − zy)^{m−1}}{(1 − 2zy)^{m−1}} .

We want to point out at that stage how to extract the diagonal from a bivariate generating function F (z, y). The procedure was first observed by Hautus and Klarner [3] but is by now almost a standard tool in combinatorial analysis.

∑_{n≥0} F (n, n)z^{n} = \frac{1}{2πi} ∫_{C} \frac{dt}{t}F (\frac{z}{t} , t),

where the curve C winds around the origin exactly once. This integral can be evaluated as a sum over the residues of F (\frac{z}{t}, t)\frac{1}{t}, over the “small” solutions t = s(z), i.e., those that satisfy s(z) → 0 for z → 0 (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.

2 A summation

The following sum was of interest for Neiter and Proag [4]

∑_{j≥0} B_{n−j,k−2j}^{[m]}.

We can be careless about the range of summation, since only terms of the form 0 ≤ k − 2j ≤ 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):

\frac{1}{1 − zy^{2}} \frac{(1 − zy)^{m−1}}{(1 − 2zy)^{m−1}(1 − z(1 + y))}.

Since the interest is/was only for n = k, we extract the diagonal from this generating function, or even from the trivariate generating function

\frac{1}{1 − zy^{2}} ∑_{m≥1} F_{m}(z, y)w^{m−1} = \frac{1}{1 − zy^{2}} \frac{1}{1 − z(1 + y)} \frac{1}{1 − \frac{w(1−zy)}{1−2zy}} .

As mentioned before, the diagonal is the contour integral

\frac{1}{2πi} ∮ \frac{dt}{t} \frac{1}{1 − zt} \frac{1}{1 − z/t(1 + t)} \frac{1 − 2z}{1 − 2z − w(1 − z)}

= \frac{1}{2πi} ∮ dt\frac{1}{1 − zt} \frac{1}{t − z(1 + t)} \frac{1 − 2z}{1 − 2z − w(1 − z)}.

There are two poles: t = 1/z and t = z/(1 − z). Only the second one is “small” and we compute the residue:

Res_{t=z/(1−z)}\{\frac{1}{1 − zt} \frac{1}{t − z(1 + t)} \frac{1 − 2z}{1 − 2z − w(1 − z)}\}

= \frac{1}{1 − z^{2}/(1 − z)} \frac{1}{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}} ∑_{m≥0} w^{m} \frac{(1 − z)^{m}}{(1 − 2z)^{m}} .

We note for further reference that

\frac{1}{1 − z − z^{2}} = ∑_{n≥0} F_{n+1}z^{n}

is the generating function of the Fibonacci numbers [2].

Let us start with the simple instance m = 1 and extract the coefficient of w^{m−1}:

\frac{1}{1 − z − z^{2}} ,

so that

∑_{j≥0} \binom{n − j}{n − 2j} = ∑_{0≤j≤n/2} \binom{n − j}{j} = F_{n+1},

which is classical.

Now we move to the instance m = 2 and extract the coefficient of w^{m−1}:

\frac{1}{1 − z − z^{2}} \frac{1 − z}{1 − 2z} = \frac{2}{1 − 2z} − \frac{1 + z}{1 − z − z^{2}} .

Reading off the coefficient of z^{n} here leads to

2^{n+1} − F_{n+1} − F_{n} = 2^{n+1} − F_{n+2},

which is the evaluation of

∑_{j≥0} B_{n−j,n−2j}^{[2]}.

By computing the partial fraction decomposition, the next few instances are

(n − 1)2^{n} + F_{n+3}, (m = 3)

(\frac{n^{2}}{4} + \frac{n}{4} + 4)2^{n} − F_{n+4}, (m = 4)

(\frac{n^{3}}{24} + \frac{n^{2}}{4} + \frac{53n}{24} − 4)2^{n} + F_{n+5}, (m = 5)

and we wonder if we can say anything in general. We can indeed apply the principle of partial fraction decomposition directly to

\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})}.

The second term is easier:

[z^{n}w^{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_{n}F_{m−1}) = (−1)^{m−1}F_{n+m}.

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

∑_{m≥1} \frac{polynomial in z of degree m − 1}{(1 − 2z)^{m}}w^{m}.

Calling the polynomials in the numerator u_{m} = u_{m}(z), Maple’s gfun command computes the following recursion:

u_{m+3} − zu_{m+2} − (2z − 1)(3z − 2)u_{m+1} − (z − 1)(2z − 1)^{2}u_{m} = 0,

with initial conditions u_{0} = 0, u_{1} = 2, u_{2} = 4z − 1.

3 A more general summation

Let c ≥ 1 be an integer. We are, as our predecessors, interested in

∑_{j≥0} B_{n−cj,k−(c+1)j}^{[m]},

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

\frac{1}{1 − z^{c}y^{c+1}} \frac{1}{1 − z(1 + y)} \frac{1}{1 − \frac{w(1−zy)}{1−2zy}} .

Extracting the diagonal leads to the computation of the residue(s) of

\frac{1}{1 − z^{c}t} \frac{1}{t − z(1 + t)} \frac{1 − 2z}{1 − 2z − w(1 − z)}.

Res_{t=z/(1−z)}\{\frac{1}{1 − z^{c}t} \frac{1}{t − z(1 + t)} \frac{1 − 2z}{1 − 2z − w(1 − z)}\}

= \frac{1}{1 − z^{c+1}/(1 − z)} \frac{1}{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}} ∑_{m≥0} w^{m} \frac{(1 − z)^{m}}{(1 − 2z)^{m}} .

The first factor generates some generalized Fibonacci number. We keep the notation of Neiter and Proag [4]:

\frac{z^{c}}{1 − z − z^{c+1}} = ∑_{n≥0} λ_{n}(c)z^{n}.

For m = 1, the coefficient of w^{m−1} leads to

\frac{1}{1 − z − z^{c+1}} = ∑_{n≥0} λ_{n+c}(c)z^{n},

and thus we have the first summation

∑_{j≥0} B_{n−cj,n−(c+1)j}^{[1]} = λ_{n+c}(c).

For m = 2, the coefficient of w^{m−1} leads to

\frac{1}{1 − z − z^{c+1}} \frac{1 − z}{1 − 2z} = \frac{2^{c}}{2^{c} − 1} \frac{1}{1 − 2z} − \frac{1}{2^{c} − 1} \frac{1 + ∑_{j=1}^{c} 2^{j−1}z^{j}}{1 − z − z^{c+1}}

and the coefficient of z^{n} is given by

\frac{2^{c}}{2^{c} − 1}2^{n} − \frac{1}{2^{c} − 1}(λ_{n+c}(c) + ∑_{j=1}^{c} 2^{j−1}λ_{n+c−j}(c)),

which is the summation for

∑_{j≥0} B_{n−cj,n−(c+1)j}^{[2]}.

We stop here since further instances become a bit clumsy.

4 Another summation

The next type of summation that we will treat with generating functions is

∑_{0≤j≤n/2} B_{n−j,j}^{[m]}.

In this case one has to be careful not to include unwanted terms in the summation. Let us start with m = 1:

∑_{0≤j≤n/2} \binom{n − j}{j} = ∑_{0≤j≤n} \binom{n − j}{j}.

We consider (again) the generating function

∑_{0≤j≤n} z^{n}\binom{n − j}{j} = ∑_{j,k≥0} z^{k}z^{j}\binom{k}{j} = \frac{1}{1 − z(1 + z)},

whence we get F_{n+1} for the summation.

Now let us move to m = 2.

∑_{0≤j≤n/2}B_{n−j,j}^{[2]} = ∑_{0≤h≤j≤n/2} \binom{n − j}{h}

= ∑_{0≤h≤j≤n} \binom{n − j}{h} − ∑_{n/2<j≤n} ∑_{h=0}^{j} \binom{n − j}{h}

= ∑_{0≤h≤j≤n} \binom{n − j}{h} − ∑_{n/2<j≤n} 2^{n−j} = ∑_{0≤h≤j≤n} \binom{n − j}{h} − 2^{⌊(n+1)/2⌋} + 1.

The generating function related to the first term is

∑_{n≥0} z^{n} ∑_{0≤h≤j≤n} \binom{n − j}{h} = ∑_{n≥0} z^{n} ∑_{0≤h≤n} \binom{n + 1 − h}{h + 1} = ∑_{h≥0} z^{h} ∑_{n≥h} z^{n−h}\binom{n + 1 − h}{h + 1}

= ∑_{h≥0} z^{h} ∑_{k≥0} z^{k}\binom{k + 1}{h + 1} = ∑_{h≥0} z^{h} \frac{z^{h}}{(1 − z)^{h+2}}

= \frac{1}{(1 − z)^{2}} \frac{1}{1 − \frac{z^{2}}{1−z}} = \frac{1}{1 − z} \frac{1}{1 − z − z^{2}} = \frac{z + 2}{1 − z − z^{2}} − \frac{1}{1 − z} .

This leads to the evaluation

F_{n} + 2F_{n+1} − 1 − 2^{⌊(n+1)/2⌋} + 1 = F_{n+3} − 2^{⌊(n+1)/2⌋}.

In the same style one can also treat the higher instances m = 3, 4, . . .. However, we would like to offer a tool that is very useful: 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

\frac{z + 2}{1 − z − z^{2}} − \frac{1 + 2z}{1 − 2z^{2}} ,

and for m = 3 to

\frac{3z + 5}{1 − z − z^{2}} − \frac{1}{2} \frac{1 + 2z}{(1 − 2z^{2})^{2}} − \frac{1}{2} \frac{7 + 12z}{(1 − 2z^{2})^{2}} ,

with result

F_{n+5} − \begin{cases}2^{k−1}(k + 8), & for n = 2k; \\ 2^{k}(k + 7), & for n = 2k + 1. \end{cases}

The reader can create further examples herself.

References

[1] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[2] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

[3] M. L. J. Hautus and D. A. Klarner, The diagonal of a double power series, Duke Math. J. 38 (1971), 229–235.

[4] D. Neiter and A. Proag, Links between sums over paths in Bernoulli’s triangles and Fibonacci numbers, J. Integer Sequences 19 (2016), Article 16.8.3.

[5] Bruno Salvy and Paul Zimmermann, Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994), 163–177.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19, 11B39. Keywords: Bernoulli triangle, generating function, diagonal of a double power series.

(Concerned with sequence \underline{A000108}.)

Received November 12 2016. Revised version received December 25 2016. Published in Journal of Integer Sequences, December 26 2016.

Return to Journal of Integer Sequences home page.