WILF’S “SNAKE OIL” METHOD PROVES AN IDENTITY

IN THE MOTZKIN TRIANGLE

Tewodros Amdeberhan, Moa Apagodu and Doron Zeilberger

Dedicated to the memory of Herb Wilf

Abstract. We give yet-another illustration of using Herb Wilf’s Snake Oil Method, by proving a certain identity between the entries of the so-called Motzkin Triangle, that arose in a recent study of enumeration of certain classes of integer partitions. We also briefly illustrate how this method can be applied to general ‘triangles’.

Our starting point was a certain conjecture, concerning the so-called simultaneous core partitions, found in a recent preprint [2, Conjecture 11.5]. It reads:

Conjecture. Let s and d be two coprime positive integers. Then the number of (s, s+d, s+2d)-core partitions is given by

∑_{k=0}^{⌊ \frac{s}{2} ⌋} \binom{s + d − 1}{2k + d − 1}\binom{2k + d}{k}\frac{1}{2k + d}.

We then paid particular interest to the special cases d = 1 (see [1]), resulting in the Motzkin numbers proven in [2] and by Yang-Zhong-Zhou [5], and d = 2 initiating yet another link [1, Problem 11.6] to the Motzkin triangle which we now state.

Problem. The Motzkin triangle T (n, k) of numbers is defined according to the rules: (1) T (n, 0) = 1;

(2) T (n, k) = 0 if k < 0 or k > n;

(3) T (n, k) = T (n − 1, k − 2) + T (n − 1, k − 1) + T (n − 1, k).

Prove the identity (this is sequence A026940 in OEIS [3]))

∑_{k=0}^{n} T (n, k)T (n, k + 1) = ∑_{k=0}^{n} \binom{2n}{2k + 1}\binom{2k + 1}{k}\frac{1}{k + 2}.

Let us first observe that any such identity is nowadays automatically provable, thanks to the so-called Wilf-Zeilberger algorithmic proof theory, but it is still fun to prove it, whenever possible, the old-fashioned way, by purely human means. We will do this, by using what Herb Wilf called the Snake-Oil method [4, Section 4.3].

Typeset by AMS-TEX

Recall that the Constant Term of a Laurent polynomial, P (x), is the coefficient of x^{0}. For example, CT [4/x + 3 + 5x] = 3. For motivation, let’s look at a few known examples.

(1) ∑_{k=0}^{n} \binom{n}{k} x^{k} = (1+x)^{n} and hence CT [\frac{(1+x)^{n}}{x^{k}} ] = \binom{n}{k}, the famous binomial coefficients as entries in the familiar Pascal’s triangle (see A007318 in OEIS [3]).

(2) ∑_{k=0}^{n+2} C(n, k) x^{k} = (1 + x)^{n}(1 − x), this is one variant among the Catalan triangles (see the sequences A008315 and A037012 in OEIS [3]).

(3) ∑_{k=0}^{2n} t(n, k) x^{k} = (1 + x + x^{2})^{n}, the trinomial triangle (see A027907 in OEIS [3]).

Going back to the Motzkin triangle , we return to our Problem by first extending the definition of the Motzkin triangle from k = 0, 1, …, n to k = 0, 1, …, 2n + 2 as a skew-symmetric sequence:

T (n, k) = −T (n, 2n − k + 2).

Note. T (n, n + 1) = 0 and the extended Motzkin triangle (we continue to denote by T (n, k)) obeys the same recurrence. As a result, it is easy to construct the generating function

∑_{k=0}^{2n+2} T (n, k)x^{k} = (1 + x + x^{2})^{n}(1 − x^{2}).

Or, equivalently, for k ∈ {0, 1, …, 2n + 2},

T (n, k) = CT (\frac{(1 + x + x^{2})^{n}(1 − x^{2})}{x^{k}}) .

So, the stage is now set and The Snake Oil method can be brought to bear:

∑_{k=0}^{n} T (n, k)T (n, k + 1) = \frac{1}{2} ∑_{k=0}^{2n+2} T (n, k)T (n, k + 1)

= \frac{1}{2} ∑_{k=0}^{2n+1} T (n, k) · CT (\frac{(1 + x + x^{2})^{n}(1 − x^{2})}{x^{k+1}})

= \frac{1}{2} CT [\frac{(1 + x + x^{2})^{n}(1 − x^{2})}{x} ∑_{k=0}^{2n+1} T (n, k)x^{−k}]

= \frac{1}{2} CT [\frac{(1 + x + x^{2})^{n}(1 − x^{2})}{x} (1 + \frac{1}{x} + \frac{1}{x^{2}} )^{n} (1 − \frac{1}{x^{2}} )]

= \frac{1}{2} CT [\frac{(1 + x + x^{2})^{2n}(1 − x^{2})}{x^{2n+1}}] − \frac{1}{2} CT [\frac{(1 + x + x^{2})^{2n}(1 − x^{2})}{x^{2n+3}}]

= \frac{1}{2} T (2n, 2n + 1) − \frac{1}{2} T (2n, 2n + 3)

= \frac{1}{2} T (2n, 2n − 1);

where the last equality is due to T (2n, 2n + 1) = 0 and T (2n, 2n + 3) = −T (2n, 2n − 1). We pause for a moment to appreciate a striking similarity between the two identities,

∑_{k=0}^{n} \binom{n}{k}\binom{n}{k + 1} = \binom{2n}{n + 1}  and  ∑_{k=0}^{n} T (n, k) T (n, k + 1) = \frac{1}{2} T (2n, 2n − 1),

involving coefficients in the Pascal’s triangle and the current Motzkin’s triangle, respectively.

On the other hand, if we expand (1 + x + x^{2})^{2n} = ((1 + x) + x^{2})^{2n} = ∑_{k=0}^{2n} \binom{2n}{k}x^{2k}(1 + x)^{2n−k} then by reverse-engineering the expression for \frac{1}{2} T (2n, 2n − 1) from above, we are led to

\frac{1}{2} T (2n, 2n − 1) = \frac{1}{2} CT [\frac{(1 + x + x^{2})^{2n}(1 − x^{2})}{x^{2n−1}}]

= \frac{1}{2} CT [\frac{(1 + x + x^{2})^{2n}}{x^{2n−1}} ] − \frac{1}{2} CT [\frac{(1 + x + x^{2})^{2n}}{x^{2n−3}} ]

= \frac{1}{2} ∑_{k=0}^{n−1} \binom{2n}{k}\binom{2n − k}{2n − 2k − 1} − \frac{1}{2} ∑_{k=0}^{n−2} \binom{2n}{k}\binom{2n − k}{2n − 2k − 3}

= \frac{1}{2} ∑_{k=0}^{n−1} \binom{2n}{2k + 1}\binom{2k + 1}{k} − \frac{1}{2} ∑_{k=0}^{n−2} \binom{2n}{2k + 3}\binom{2k + 3}{k}

= n + \frac{1}{2} ∑_{k=1}^{n−1} \binom{2n}{2k + 1}\binom{2k + 1}{k} − \frac{1}{2} ∑_{k=1}^{n−1} \binom{2n}{2k + 1}\binom{2k + 1}{k − 1}

= n + ∑_{k=1}^{n−1} \binom{2n}{2k + 1}\binom{2k + 1}{k}\frac{1}{k + 2} = ∑_{k=0}^{n−1} \binom{2n}{2k + 1}\binom{2k + 1}{k}\frac{1}{k + 2},

which is exactly the right-hand side of our problem. This completes the proof. In fact, we have improved the assertion of Problem 11.6 because of our success in evaluating the two sums into the simpler form \frac{1}{2}T (2n, 2n − 1). Therefore, we may formulate our conclusion as the next result.

Theorem 1. The following identities hold true:

∑_{k=0}^{n} T (n, k)T (n, k + 1) = ∑_{k=0}^{n} \binom{2n}{2k + 1}\binom{2k + 1}{k}\frac{1}{k + 2} = \frac{1}{2} T (2n, 2n − 1).

A litmus test (or a cannon measure, if you prefer) to the quality of a good technique is perhaps its enlightenment, simplicity and implications. Indeed, in our case, the linear operator CT offers both a clue to and a proof for an effortless generalization of Theorem 1. The Motzkin triangle persists!

Theorem 2. The following identity holds true:

∑_{k=0}^{⌊ \frac{s}{2} ⌋} \binom{s + d − 1}{2k + d − 1}\binom{2k + d − 1}{k}\frac{1}{k + d} = \frac{1}{d} T (s + d − 1, s).

Proof. This is completely analogous to what has been demonstrated earlier. To wit,

\frac{1}{d} T (s + d − 1, s) = \frac{1}{d} CT [\frac{(1 + x + x^{2})^{s+d−1}}{x^{s}} ] − \frac{1}{d} CT [\frac{(1 + x + x^{2})^{s+d−1}}{x^{s−2}} ]

= \frac{1}{d} ∑_{k≥0} \binom{s + d − 1}{k}\binom{s + d − k − 1}{s − 2k} − \frac{1}{d} ∑_{k≥0} \binom{s + d − 1}{k}\binom{s + d − k − 1}{s − 2k − 2}

= \frac{1}{d} ∑_{k≥0} \binom{s + d − 1}{2k + d − 1}\binom{2k + d − 1}{k} − \frac{1}{d} ∑_{k≥0} \binom{s + d − 1}{2k + d + 1}\binom{2k + d + 1}{k}

= ∑_{k≥0} \binom{s + d − 1}{2k + d − 1}\binom{2k + d − 1}{k}\frac{1}{k + d}.

The proof is complete. □

Is there more? Yes, here is a bonus! As a nice implication of the preceding results, the above Conjecture may be stated much more succinctly.

Conjecture. If s, d ≥ 1 are coprime integers, then the number of (s, s + d, s + 2d)-core partitions equals

\frac{1}{d} T (s + d − 1, s).

General Triangles. The above method of proof extends to a much wider class of triangle of numbers generated by the family

{P (x)^{n}Q(x) : n ∈ ℕ}

where the polynomial P (x) is palindromic. For the sake of simplicity we will take Q(x) = 1 − x^{2}. Consider for instance the sequence A(n, k) defined by the recurrence

A(n, k) = a_{0}A(n − 1, k) + a_{1}A(n − 1, k − 1) + ⋯ + a_{d}A(n − 1, k − d)

satisfying some initial conditions and where a_{j} = a_{d−j} for j ∈ {0, 1, …, d} (palindromic coefficients). As before, extend the definition of A(n, k) as skew-symmetric. If we take P (x) = ∑_{j=0}^{d} a_{j}x^{j} and Q(x) = 1 − x^{2} then

∑_{k≥0} A(n, k) x^{k} = P (x)^{n}Q(x).

Once more, The Snake Oil method delivers the argument almost verbatim:

∑_{k=0}^{dn/2} A(n, k)A(n, k + 1) = \frac{1}{2} ∑_{k=0}^{dn+2} A(n, k)A(n, k + 1)

= \frac{1}{2} ∑_{k=0}^{dn+2} A(n, k) · CT (\frac{P (x)^{n}(1 − x^{2})}{x^{k+1}})

= \frac{1}{2} CT [\frac{P (x)^{n}(1 − x^{2})}{x} ∑_{k=0}^{dn+2} A(n, k)x^{−k}]

= \frac{1}{2} CT [\frac{P (x)^{n}(1 − x^{2})}{x}P (1/x)^{n} (1 − \frac{1}{x^{2}} )]

= \frac{1}{2} CT [\frac{P (x)^{2n}(1 − x^{2})}{x^{dn+1}} (1 − \frac{1}{x^{2}} )]

= \frac{1}{2} CT [\frac{P (x)^{2n}(1 − x^{2})}{x^{dn+1}}] − \frac{1}{2} CT [\frac{P (x)^{2n}(1 − x^{2})}{x^{dn+3}}]

= \frac{1}{2} A(2n, dn + 1) − \frac{1}{2} A(2n, dn + 3)

= \frac{1}{2} A(2n, dn − 1);

where the last equality is due to A(2n, dn + 1) = 0 and A(2n, dn + 3) = −A(2n, dn − 1).

References

[1] T. Amdeberhan, Theorems, problems and conjectures,, arXiv:1207.4045.

[2] T. Amdeberhan, E. S. Leven, Multi-cores, posets, and lattice paths, arXiv:1406.2250.

[3] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://www.oeis.org.

[4] H Wilf, generatingfunctionology, 3rd edition, A K Peters, Ltd., MA, USA (2006).

[2nd ed. (free download): https://www.math.upenn.edu/~wilf/DownldGF.html]

[5] J Yang, M Zhong, R Zhou, On the enumeration of (s, s + 1, s + 2)-core partitions, European J Combin. 49

 (2015), 203-217.

Tulane University, Department of Math., 6823 St. Charles Av, New Orleans, LA 70118

E-mail address: tamdeber@tulane.edu

Virginia Commonwealth University, Department of Math. & Applied Math., Richmond, VA 23284

E-mail address: mapagodu@vcu.edu

Rutgers University, Department of Math., 110 Frelinghuysen Rd, Piscataway, NJ 08854

E-mail address: zeilberg@math.rutgers.edu