Two methods for determining combinatorial identities

Two methods are presented for determining advanced combinatorial identities. The first is based on extending the original identity so that it can be expressed in terms of hypergeometric functions whereupon tabulated values of the functions can be used to reduce the identity to a simpler form. The second is a computer method based on Koepf's version of the Wilf-Zeilberger approach that has been implemented in a suite of intrinsic routines in Maple. As a consequence, some new identities are presented.

Introduction

According to a Vimeo talk delivered at Rutgers in 2014, Weintraub [1] claims the following result:

${\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^n}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}n+j+1\\ n\end{array}\right)\mathrm{<mo>=</mo>1,}\text{ (1}\text{.1)}$

can only be proved by using the Wilf-Zeilberger approach. As stated in the talk, Weintraub was unable to solve the problem by himself initially. It was eventually solved by his student, Li. In fact, Li is given credit for the solution in the article stemming from the talk [2]. The point of this note is to show by way of examples that one can often extend existing techniques to solve advanced combinatoric identities such as (1.1), even though, as will be seen here later, the Wilf-Zeilberger approach is an extremely powerful method when utilized in the Maple mathematical software package.

Proof

In this section, we shall prove (1.1) by extending the result to a Gaussian hypergeometric form. However, before presenting a general proof, it should be mentioned that (1.1) can be shown to hold numerically by programming the Left-Hand Side (LHS) in Mathematica [3] as

F[n_] := Sum[(-1) ∧ (n - j) Binomial[n, j] Binomial[n + j + 1, n], {j, 0, n} ].

If one types

Timing[F[389]],

then following output is produced

{0.002959, 1}.

This means it takes a Venom laptop with 64 Gb RAM almost 0.003 CPU seconds to compute that the sum yields unity when n = 389. Obviously, the calculation will slow down drastically as n increases.

To prove that (1.1) holds for all values of n, we note that the sum on the LHS can be extended to infinity since 1/(n-j)! in the first binomial factor vanishes j ≥ n. Then the LHS can be expressed as

${\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^n}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j}n\mathrm{<mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}n-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}j\mathrm{<mo>!</mo>}}\frac{\mathrm{<mo\; stretchy="false">(</mo>}n+j+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}n\mathrm{<mo>!</mo>}}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^n{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{2<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{2<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{.}\text{ (2}\text{.1)}$

In obtaining this result, the reflection formula for the gamma function or No. 8.334 in [4] has been applied. This yields

$\frac{n\mathrm{<mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}n-j+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\frac{\sin \mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}\pi \mathrm{<mo\; stretchy="false">)</mo>}}{\sin \mathrm{<mo\; stretchy="false">(</mo>}-n\pi \mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^j\mathrm{.}\text{ (2}\text{.2)}$

By multiplying and dividing (1.1) by (n+1), one obtains

$\begin{array}{l}\text{l}hs\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^n\mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>2<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{2<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{2<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{2<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\text{ (2}\text{.3)}\\ {\mathrm{<mo\; stretchy="false">(</mo>}}^{-}{\mathrm{<mo\; stretchy="false">(</mo>}}_n{F}_1\mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{,}n+\mathrm{2<mo>;</mo>2<mo>;</mo>1<mo\; stretchy="false">)</mo>.}\end{array}$

Thus, by extending the finite sum to infinity on the LHS of (1.1), we have been able to express the LHS of the combinatorial identity as a particular case of a Gaussian hypergeometric function 2F1(a,b;c;1). Often these reduce to simple analytic results when their parameters appear in tables of the special functions. However, in this case, if we scan the table of Gaussian hypergeometric functions in Prudnikov, et al. [5], then we find that there is no listing for the parameters, a = -n, b = n+2 and c = 2. The nearest one can get to this Gaussian hypergeometric function in (2.3) is the case where a = -n, b = n+2 and c = 1. That is, according to No. 7.3.1.188 on p. 467 of [5], we have , where P_n(1-2z) represents a shifted Legendre polynomial since the argument is 1-2z. This means that in order to derive (1.1), we need to investigate whether (2.3) can be expressed in terms of shifted Legendre polynomials.

Returning to (2.1), one can re-write it as

${\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^n}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}n+j+1\\ n\end{array}\right)\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^n{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{\mathrm{<mo\; stretchy="false">(</mo>}n+j+\mathrm{1<mo\; stretchy="false">)</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{,}\text{ (2}\text{.4)}$

In order to handle the j term in the numerator, one splits the RHS of (2.4) into two separate contributions, one that will result in a Gaussian hypergeometric of unity and the other becoming a simple integration of a Gaussian hypergeometric function. Therefore, (2.4) can be expressed as

${\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^n}{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n-j}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}n+j+1\\ n\end{array}\right)\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^n{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}$

$+{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^{n}n{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\displaystyle {\int }_0^1}{x}^{j}dx\mathrm{.}\text{ (2}\text{.5)}$

The first sum on the RHS of (2.5) represents the Gaussian hypergeometric function ₂F₁(-n, n + 1;1;1) or the z = 0 case of the shifted Legendre polynomial of the index n mentioned above. As a consequence, we find that P_n(-1 = (-1)ⁿ. Multiplying by the (-1)ⁿ factor outside the first term on the right-hand side (RHS) of (2.5) yields unity as given on the RHS of the identity of (1.1). Therefore, to derive (1.1), we need to show that the second sum on the RHS of (2.5) vanishes. This sum can be expressed as

$\begin{array}{l}{\mathrm{<mo\; stretchy="false">(</mo>}}^{-}n{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\displaystyle {\int }_0^1}{x}^{j}dx\mathrm{<mo>=</mo>}\\ {\mathrm{<mo\; stretchy="false">(</mo>}}^{-}n{\displaystyle {\int }_0^1}dx{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}{x}^{j}dx\mathrm{.}\text{ (2}\text{.6)}\end{array}$

Hence the integral is now over the Gaussian hypergeometric function in [5]. In other words, we have

$\begin{array}{l}{\mathrm{<mo\; stretchy="false">(</mo>}}^{-}n{\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^{\infty }}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-n\mathrm{<mo\; stretchy="false">)</mo>}}{j\mathrm{<mo>!</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{<mo\; stretchy="false">)</mo>}}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j+n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\mathrm{1<mo\; stretchy="false">)</mo>}}{\displaystyle {\int }_0^1}{x}^{j}dx\mathrm{<mo>=</mo>}\text{ (2}\text{.7)}\\ {\mathrm{<mo\; stretchy="false">(</mo>}}^{-}n{\displaystyle {\int }_0^1}{P}_n\mathrm{<mo\; stretchy="false">(</mo>1}-2x\mathrm{<mo\; stretchy="false">)</mo>}dx\mathrm{.}\end{array}$

Carrying out a change of variable, namely, y = 1 - 2x, converts the integral to one over P_n(y) between -1 and 1. By employing [6], we arrive at

${\displaystyle {\int }_{-a}^a}{\mathrm{<mo\; stretchy="false">(</mo>}x+a\mathrm{<mo\; stretchy="false">)</mo>}}^{\alpha -1}{P}_n\mathrm{<mo\; stretchy="false">(</mo>}x\mathrm{<mo>/</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}dx\mathrm{<mo>=</mo>}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^n{\mathrm{<mo\; stretchy="false">(</mo>1}-\alpha \mathrm{<mo\; stretchy="false">)</mo>}}_n}{{\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>}}_{n+1}}\mathrm{,}\text{ (2}\text{.8)}$

where the Pochhammer symbol, ${\mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>}}_n\mathrm{<mo>=</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}n+\alpha \mathrm{<mo\; stretchy="false">)</mo><mo>/</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}\alpha \mathrm{<mo\; stretchy="false">)</mo>}$ , and $\Re \alpha$ are greater than zero. Moreover, in our case of interest, a = 1 and α = 1, means the integral vanishes due to the appearance of Γ(1 - α) the denominator on the RHS. Therefore, contrary to Weintraub in [1], the identity has been proved without having to apply the Wilf-Zeilberger algorithm. In addition, from (2.5) we have

${\displaystyle {\int }_0^1}{}_2{F}_1\mathrm{<mo\; stretchy="false">(</mo>}-n\mathrm{,}n+\mathrm{1<mo>;</mo>1<mo>;</mo>}x\mathrm{<mo\; stretchy="false">)</mo>}dx\mathrm{<mo>=</mo>0.}\text{ (2}\text{.9)}$

More advanced examples

In this section, we shall present an example where both methods can be used to establish a combinatorial identity. When applying the Wilf-Zeilberger algorithm, we shall use routines/instructions in Maple, which may appear to the reader as a black box. By the application of the extended hypergeometric function method described in the previous section, it is hoped that the reader will develop the confidence to apply the Wilf-Zeilberger approach to situations where it is no longer a simple matter to employ standard techniques.

Theorem 3.1

For positive integer values of m, the following combinatorial identity holds:

${\displaystyle \sum _{j\mathrm{<mo>=</mo>0}}^m}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^j\mathrm{<mo\; stretchy="false">(</mo>}i-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{j\mathrm{<mo>!</mo>}\mathrm{<mo\; stretchy="false">(</mo>}-j+m\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}\mathrm{<mo\; stretchy="false">(</mo>}i-j-m-q+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo>}\left(\begin{array}{c}m+q-1\\ m\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}i-m-q+\mathrm{2<mo\; stretchy="false">)</mo>}}_{q-1}\mathrm{.}\text{ (3}\text{.1)}$

The above result arose in a study of the properties of Fibonacci polynomials, which has yet to be published.

Before presenting the proof, let us verify (3.1) numerically. After all, if one can show that the result does not hold numerically, then there is no point setting about finding a proof. First, we program the LHS by using the Sum routine in Mathematica [3] as follows:

F[m_, q _, I _] := Sum[(-1)j (i - j)!/(j! (m - j)! (i - j - m - q + 1)!), {j, 0, m}].

Next, we program the RHS with the aid of the Pochhammer and Binomial functions in Mathematica. Thus we set

F2[m _, q _, I _] := Binomial[m + q - 1, m] Pochhammer[i - m - q + 2, q - 1].

Therefore, as long as m is an integer, we should observe that both instructions should give identical values for the same values of m, q and i. For example, putting m = 4, q = 1/3 and I = 7/5, and using the Simplify routine gives

In[9]:= Simplify[F[4, 1/3, 7/5]],

Out[9]= 1/24 ((-(13/5))!/(-(89/15))! - (4 (-(8/5))!)/(-(74/15))! + (6 (-(3/5))!)/(-(59/15))! - ( 4 (2/5)!)/(-(44/15))! + (7/5)!/(-(29/15))!).

In NumberForm this yields a value of -0.02144385036349257. On the other hand, if we type

In[12]:= F2[4, 1/3, 7/5],

Out[12]= (35 Gamma[-(8/5)])/(243 Gamma[-(14/15)]).

In NumberForm this yields a value of -0.02144385036349148. In both cases, results agree up to the last three decimal places. The slight difference in the numerical results is due to machine precision being invoked in number form. Now we turn to the proof of Theorem 3.1.

Proof: We shall first prove this lemma by extending the LHS of (2.8) to Gaussian hypergeometric functions. In the second proof, we shall make use of Zeilberger's algorithm to demonstrate that a computer approach is just as valid as standard analytic methods in proving combinatorial identities.

Method 1

We begin by extending the summation over j on the LHS of (2.8) to infinity, which has no effect on the result. With the aid of the reflection formula for the gamma function or No. 8.334(3) in [4], we can make the following substitutions in the LHS:

$\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}m-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^{m-i}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-m\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}j-i\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\frac{{\mathrm{<mo\; stretchy="false">(</mo>}-m\mathrm{<mo\; stretchy="false">)</mo>}}_j}{{\mathrm{<mo\; stretchy="false">(</mo>}-i\mathrm{<mo\; stretchy="false">)</mo>}}_j}\frac{i\mathrm{<mo>!</mo>}}{m\mathrm{<mo>!</mo>}}\mathrm{,}\text{ (3}\text{.2)}$

and

$\frac{1}{\mathrm{<mo\; stretchy="false">(</mo>}i-j-m-q+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^j\frac{{\mathrm{<mo\; stretchy="false">(</mo>}m+q-i-\mathrm{1<mo\; stretchy="false">)</mo>}}_j}{\mathrm{<mo\; stretchy="false">(</mo>}i-m-q+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}\text{ (3}\text{.3)}$

Then the LHS can be re-written as

$\text{l}hs\mathrm{<mo>=</mo>}\frac{i\mathrm{<mo>!</mo>}}{m\mathrm{<mo>!</mo><mo\; stretchy="false">(</mo>}i-m-q+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}{}_2{F}_1\mathrm{<mo\; stretchy="false">(</mo>}-m\mathrm{,}m+q-i-\mathrm{1<mo>;</mo>}-i\mathrm{<mo>;</mo>1<mo\; stretchy="false">)</mo>.}\text{ (3}\text{.4)}$

Next, we employ Gauss's identity for ₂F₁ hypergeometric functions when z=1, i.e., No. 9.122 in [4]. This yields

$\begin{array}{l}{}_2{F}_1\mathrm{<mo\; stretchy="false">(</mo>}-m\mathrm{,}m+q-i-\mathrm{1<mo>;</mo>}-i\mathrm{<mo>;</mo>1<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-q\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>1}-q-m\mathrm{<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-i\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}m-i\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo>}\text{ (3}\text{.5)}\\ \frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}q+m\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}q\mathrm{<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i+1-m\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i+\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{.}\end{array}$

The last member in the above result has been obtained by applying the reflection formula for the gamma function on this occasion to the intermediate member. By substituting the last result for the hypergeometric function in (3.5) and carrying out a little algebra, we obtain the RHS of (3.1).

Method 2

To apply the Wilf-Zeilberger algorithm, first described in [7] and discussed at length in [8], we set

$A_{i,q,m}={\displaystyle \sum _{j=0}^m}\frac{{(-1)}^j(i-j)!}{j!(-j+m)!(i-j-m-q+\text{1})!}.\text{ (3}\text{.6)}$

Now we replace $\mathrm{<mo\; stretchy="false">(</mo>}i-j\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo>/</mo><mo\; stretchy="false">(</mo>}i-j-m-1+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}$ by $\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-j+\mathrm{1<mo\; stretchy="false">)</mo><mo>/</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-j-m-q+\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}$ , which, in turn, means that it is in a form where one can apply Zeilberger's algorithm [9] to the sum. Next one programs the sum into Maple by using the sum command as follows:

$>sum\left(\frac{{(-1)}^{j}GAMMA(1+i+j)}{j!(-j+m)!GAMMA(2+i-j-m-q)},j=\text{0}\mathrm{..}m\right)$

Then we type in the command with (sumtools): .

This is a suite of commands for computing both definite and indefinite sums. Koepf's version [8] of Zeilberger's algorithm appears as the sumrecursion routine in this suite. It calculates a downward recurrence relation for the above sum. Therefore typing

$\mathrm{<mo>></mo>}sumrecursion({\mathrm{<mo\; stretchy="false">(</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}}^j\mathrm{<mo>*</mo>}\text{G}AMMA\mathrm{<mo\; stretchy="false">(</mo>1}+i-j\mathrm{<mo\; stretchy="false">)</mo><mo>/</mo>}$

$\mathrm{<mo\; stretchy="false">(</mo>}j\mathrm{<mo>!</mo><mo>*</mo><mo\; stretchy="false">(</mo>}-j+m\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo>*</mo>}\text{G}AMMA\mathrm{<mo\; stretchy="false">(</mo>2}+i-j-m-q\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>,}j\mathrm{,}A\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>})$

results in the following output:

-(-1 + m + q) (2 + i - m - q) A(m - 1) + A(m) m (i - m + 1).

By replacing m by m+1, we can express the above first order recurrence relation or difference equation with respect to m in a better form as

$\mathrm{<mo\; stretchy="false">(</mo>}m+\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}i-m\mathrm{<mo\; stretchy="false">)</mo>}{A}_{i\mathrm{,}q\mathrm{,}m+1}-\mathrm{<mo\; stretchy="false">(</mo>}q+m\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}i-q-m+\mathrm{1<mo\; stretchy="false">)</mo>}{A}_{i\mathrm{,}q\mathrm{,}m}\mathrm{<mo>=</mo>0,}\text{ (3}\text{.7)}$

with the initial value or m = 0 value of both sides of (2.8) given by

$\mathrm{<mo\; stretchy="false">(</mo>}m+\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}i-m\mathrm{<mo\; stretchy="false">)</mo>}{A}_{i\mathrm{,}q\mathrm{,}m+1}-\mathrm{<mo\; stretchy="false">(</mo>}q+m\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}i-q-m+\mathrm{1<mo\; stretchy="false">)</mo>}{A}_{i\mathrm{,}q\mathrm{,}m}\mathrm{<mo>=</mo>}\text{0}\mathrm{,}$

The recurrence relation given by (3.7) can be solved easily by inspection. Therefore, we find that A_i,q,m is given by

$A_{i\mathrm{,}q\mathrm{,}m}\mathrm{<mo>=</mo>}\left(\begin{array}{c}m+q-1\\ m\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>}i-m-q+\mathrm{2<mo\; stretchy="false">)</mo>}}_{q-1}\mathrm{,}\text{ (3}\text{.9)}$

which represents the RHS of (3.1).

Now we turn our attention to a more complicated combinatorial sum, where the representation of the summand in terms of hypergeometric function is somewhat problematic, and using the Wilf-Zeilberger algorithm as implemented in Maple is the better option.

In the course of studying repeated integrations of the Fibonacci polynomials, we came across the following sum:

$M_{i\mathrm{,}q\mathrm{,}\ell }\mathrm{<mo>=</mo>}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{\ell }}\frac{\mathrm{<mo\; stretchy="false">(</mo>1}+i-2p+q\mathrm{<mo\; stretchy="false">)</mo>}\left(\begin{array}{c}q\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>1}+i-2\ell +q\mathrm{<mo\; stretchy="false">)</mo>}}_{\ell -p}}{\mathrm{<mo\; stretchy="false">(</mo>}\ell -p\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>1}+i-p{\mathrm{<mo\; stretchy="false">)</mo>}}_{q+1}}\mathrm{.}\text{ (3}\text{.10)}$

The question is whether the above sum can be reduced to a simpler form.

It should be mentioned that (3.10) can be expressed as the sum of two related 3F2 hypergeometric functions by extending the sum over p to infinity as in previous examples. Consequently, (3.10) can be expressed as

$M_{i\mathrm{,}q\mathrm{,}\ell }\mathrm{<mo>=</mo>}\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-2l+q+\mathrm{1<mo\; stretchy="false">)</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{\infty }}\frac{q\mathrm{<mo>!</mo>}}{p\mathrm{<mo>!</mo><mo\; stretchy="false">(</mo>}q-p\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-l-p-q+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}l-p+\mathrm{1<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-p+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i+q-p+\mathrm{1<mo\; stretchy="false">)</mo>}}$

$-\frac{1}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-2l+q+\mathrm{1<mo\; stretchy="false">)</mo>}}{\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{\infty }}\frac{q\mathrm{<mo>!</mo>}}{p\mathrm{<mo>!</mo><mo\; stretchy="false">(</mo>}q-p-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-l-p+q\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}l-p\mathrm{<mo\; stretchy="false">)</mo>}}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-p\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i+q-p+\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{.}\text{ (3}\text{.11)}$

Next, we replace all the ratios of the gamma functions with negative p arguments with ratios with positive p arguments using the reflection formula or No. 8.334 in [4]. For example, we write $q\mathrm{<mo>!</mo><mo>/</mo><mo\; stretchy="false">(</mo>}q-p\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^p\Gamma \mathrm{<mo\; stretchy="false">(</mo>}p-q\mathrm{<mo\; stretchy="false">)</mo><mo>/</mo>}\Gamma \mathrm{<mo\; stretchy="false">(</mo>}-q\mathrm{<mo\; stretchy="false">)</mo>}$ , then

$\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}i-l-p+q+\mathrm{1<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}l-p+\mathrm{1<mo\; stretchy="false">)</mo>}}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-{\mathrm{1<mo\; stretchy="false">)</mo>}}^{i+q}\frac{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}p-l\mathrm{<mo\; stretchy="false">)</mo>}}{\Gamma \mathrm{<mo\; stretchy="false">(</mo>}p+l-q-i\mathrm{<mo\; stretchy="false">)</mo>}}\mathrm{,}\text{ (3}\text{.12)}$

and so on for the other ratios. As a consequence, (3.11) becomes

$\begin{array}{l}{M}_{i,q,l}=\frac{{(-1)}^i}{\Gamma (i-2l+q+1)}{\displaystyle \sum _{p=0}^{\infty }}\frac{{(-1)}^p}{p!}\frac{\Gamma (p-q)}{\Gamma (-q)}\frac{\Gamma (p-l)\Gamma (l-q-i)}{\Gamma (-l)\Gamma (p+l-q-i)}\frac{\Gamma (p-q-i)\Gamma (-i)}{\Gamma (-q-i)\Gamma (p-i)}\\ \times \frac{\Gamma (-l)\Gamma (-q-i)}{\Gamma (l-q-i)\Gamma (-i)}+\frac{{(-1)}^{i}q}{\Gamma (i-2l+q+1)}{\displaystyle \sum _{p=0}^{\infty }}\frac{{(-1)}^p}{p!}\frac{\Gamma (p+1-q)}{\Gamma (1-q)}\frac{\Gamma (p+1-l)}{\Gamma (1-l)}\\ \times \frac{\Gamma (1+l-q-i)}{\Gamma (p+1+l-q-i)}\frac{\Gamma (p-q-i)\Gamma (1-i)}{\Gamma (-q-i)\Gamma (p+1-i)}\frac{\Gamma (1-l)\Gamma (-q-i)}{\Gamma (1+l-q-i)\Gamma (1-i)}.\text{(3}\text{.13)}\end{array}$

In the above equation, the infinite sums over p represent two different 3F2 hypergeometric functions with the argument equal to -1. Thus, (3.13) reduces to

$\begin{array}{l}{M}_{i,q,l}=\frac{(q+i-l-1)!(i-1)!}{(i-2l+q)!l!(q+i)!}((q+i-l)i{}_3{F}_2(-q,-l,-q-i;l-q-i,-i;-1)\\ -ql{}_3{F}_2(1-q,1-l,-q-i;1+l-q-i,1-i;-1)).(3.14)\end{array}$

As in the case of Theorem 3.1, we can obtain a much simpler form of (3.10) by inserting it into Maple and applying Zeilberger's algorithm using the sumrecursion routine. The output generated by this routine is:

-(2 + i - 2*l + q)*(1 + i - 2*l + q)*M(l - 1) + M(l)*l*(1 + i - l).

Now we replace l by l+1 and set the output equal to zero. Therefore, we arrive at the following recurrence relation:

$\mathrm{<mo\; stretchy="false">(</mo>}\ell +\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}-\ell +i\mathrm{<mo\; stretchy="false">)</mo>}{M}_{i\mathrm{,}q\mathrm{,}\ell +1}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}-2\ell +i+q-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}-2\ell +i+q\mathrm{<mo\; stretchy="false">)</mo>}{M}_{i\mathrm{,}q\mathrm{,}\ell }\mathrm{,}\text{ (3}\text{.15)}$

where the initial value is given by

$M_{i\mathrm{,}q\mathrm{,0}}\mathrm{<mo>=</mo>}\frac{i\mathrm{<mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}i+q\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}\text{ (3}\text{.16)}$

Again, this can be solved easily and yields

$M_{i\mathrm{,}q\mathrm{,}\ell }\mathrm{<mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\ell \mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{\ell \mathrm{<mo>!</mo>}\mathrm{<mo\; stretchy="false">(</mo>}i-2\ell +q\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}\text{ (3}\text{.17)}$

Thus, the sum over p in (3.10) simplifies to

${\displaystyle \sum _{p\mathrm{<mo>=</mo>0}}^{\ell }}\frac{\mathrm{<mo\; stretchy="false">(</mo>1}+i-2p+q\mathrm{<mo\; stretchy="false">)</mo>}\left(\begin{array}{c}q\\ p\end{array}\right){\mathrm{<mo\; stretchy="false">(</mo>1}+i-2\ell +q\mathrm{<mo\; stretchy="false">)</mo>}}_{\ell -p}}{\mathrm{<mo\; stretchy="false">(</mo>}\ell -p\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>1}+i-p{\mathrm{<mo\; stretchy="false">)</mo>}}_{q+1}}\mathrm{<mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\ell \mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{\ell \mathrm{<mo>!</mo><mo\; stretchy="false">(</mo>}i-2\ell +q\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}\text{ (3}\text{.18)}$

As an interesting aside, we can equate (3.17) with (3.11), thereby obtaining

$\mathrm{<mo\; stretchy="false">(</mo>}q+i-l\mathrm{<mo\; stretchy="false">)</mo>}i{}_3{F}_2\mathrm{<mo\; stretchy="false">(</mo>}-q\mathrm{,}-l\mathrm{,}-q-i\mathrm{<mo>;</mo>}l-q-i\mathrm{,}-i\mathrm{<mo>;</mo>}-\mathrm{1<mo\; stretchy="false">)</mo>}$

$-ql{}_3{F}_2\mathrm{<mo\; stretchy="false">(</mo>1}-q\mathrm{,1}-l\mathrm{,}-q-i\mathrm{<mo>;</mo>1}+l-q-i\mathrm{,1}-i\mathrm{<mo>;</mo>}-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\ell \mathrm{<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}q+i\mathrm{<mo\; stretchy="false">)</mo><mo>!</mo>}}{\mathrm{<mo\; stretchy="false">(</mo>}q+i-l-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo><mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo>!</mo>}}\mathrm{.}\text{ (3}\text{.19)}$

Moreover, we can verify this result in Mathematica [3] by creating the following instructions:

P[i_,l_,q_] := Gamma[i - l + 1] Gamma[i + q + 1]/(Gamma[i + q - l] Gamma[i]),

and

P2[i_,l_,q_] := (i + q -l) i HypergeometricPFQ[{-q, -l, -q - i}, {l - q - i, -i}, -1] - q l HypergeometricPFQ[{1 - q, 1 - l, -i - q}, {1 + l - q - i, 1 - i}, -1].

If we let i = 12, q = 7 and l = 8, then we obtain the following results:

In[3]:= P[12, 7, 8]

Out[3]= 167960/11,

and

In[8]:= P2[12, 7, 8]

Out[8]= 167960/11.

Therefore, we observe that both sides of (3.19) agree with each other. As a consequence, it should be noted that even when the hypergeometric function approach is not able to produce an elegant solution to a combinatorial identity, it can provide new results for hypergeometric functions in conjunction with the Wilf-Zeilberger approach.

Conclusion

In the first approach the combinatorial identity is expressed in terms of a hypergeometric function, not necessarily a Gaussian hypergeometric function, and then adapted into a form where it can be determined from existing tables of hypergeometric functions such as those in [6] or in the Mathematica software package. The second approach has been the application of Koepf's version [8] of the Wilf-Zeilberger algorithm [7], which is an existing suite of routines in Maple. Both methods have their strengths and weaknesses as described herein. Nevertheless, we have used both methods to solve some tricky combinatorial identities.

1. Weintraub SH. The Adjoint of Differentiation, delivered in the Experimental Mathematics seminar, Rutgers University. Nov 6 2014. https://vimeo.com/111794318 & https://vimeo.com/111794317.
2. Weintraub SH. The Adjoint of Differentiation, Experimental Mathematics. 2014; 23:429-432.
3. Wolfram S. Mathematica- A System for Doing Mathematics by Computer, Addison-Wesley, Reading, Massachusetts. 1992.
4. Gradshteyn IS, Ryzhik IM, Jeffrey A (Eds.). Table of Integrals, Series and Products, Fifth Ed., Academic Press, London, USA. 1994.
5. Prudnikov AP, Brychkov YuA, Marichev OI. Integrals and Series, Vol. 3: More Special Functions, Gordon and Breach, New York. 1990.
6. Prudnikov AP, Brychkov YuA, Marichev OI. Integrals and Series. Special Functions, Gordon and Breach, New York. 1986; 2:421.
7. Wilf HS, Zeilberger D. Rational Functions Certify Combinatorial Identities, J. Amer. Math. Soc. 1990; 3:147-158.
8. Koepf W. Hypergeometric summation. Vieweg, Braunschweig/Wiesbaden. 1998.
9. Zeilberger D. A Fast Algorithm for Proving Terminating Hypergeometric Identities, Discrete Math. 1990; 80(2):207-211.