Combinatorial sums derived from properties of Legendre polynomials

1. Problem Statement

The paper addresses the challenge of finding closed-form expressions for specific classes of combinatorial sums involving binomial coefficients, alternating signs, and rational terms. These sums often appear in number theory and combinatorics but are difficult to evaluate using standard algebraic manipulation alone. The authors aim to bridge the gap between these discrete sums and the continuous properties of Legendre polynomials ($P_n(x)$), specifically utilizing their generating functions, orthogonality, and integral representations to derive exact solutions.

2. Methodology

The authors employ a multi-step methodology combining generating functions, coefficient extraction, and integral calculus:

• Coefficient Extraction Identity (Lemma 2.1): The foundation of the work is a specific identity linking a combinatorial sum to the coefficient of a transformed generating function. Specifically, they relate a sum involving terms like $\binom{n+k}{2k}$ to the coefficient $[z^n]$ of the function $\frac{1-z}{1+z} F\left(\frac{z}{(1+z)^2}\right)$.
• Connection to Legendre Polynomials: By choosing specific generating functions $F(z)$ (e.g., related to $(1+xz)^{-1/2}$), the authors map the combinatorial sums directly to Legendre polynomials evaluated at specific arguments. This allows them to express sums in terms of $P_n(x)$ and $P_{n-1}(x)$.
• Integration Techniques: To evaluate sums containing denominators like $(n+k)$, $(k+1)$, or $(2k+2\mu)$, the authors integrate the derived polynomial identities.
  • They utilize the orthogonality property $\int_{-1}^1 P_n(x)P_m(x)dx = 0$ (for $n \neq m$) and the specific property $\int_{-1}^1 P_n(x)dx = 0$ for $n \geq 1$.
  • They employ known integral formulas involving Legendre polynomials, such as $\int_0^1 x^{2\mu-1} P_n(2x^2-1)dx$, often referencing standard tables like Gradshteyn and Ryzhik.
  • For sums involving squared denominators (e.g., $(k+1)^2$), they utilize integrals involving $\ln(1/x)$ and the function $\arcsin(x)$, leveraging the Gautschi formula and properties of odd/even functions.

3. Key Contributions and Results

A. General Identity Linking Sums and Polynomials

The primary contribution is Theorem 2.2, which establishes a general closed form for a broad class of sums:
$$\sum_{k=0}^n \binom{n+k}{2k} \binom{2k}{k} \frac{2^{-2k}}{n+k} x^k = \frac{(-1)^n}{2^n} \left[ P_n\left(\frac{-x+2}{2}\right) - P_{n-1}\left(\frac{-x+2}{2}\right) \right]$$
This identity serves as the "master key" from which numerous specific results are derived.

B. Specific Combinatorial Identities

Using the master identity and integration techniques, the authors derive several specific closed forms:

1. Vanishing Sums:

   • They prove that for $n \geq 1$, $\sum_{k=0}^n \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{n+k} = 0$ (Corollary 2.5).
   • They derive conditions where sums involving $(n+k)(k+1)$ vanish for $n \geq 2$ (Proposition 3.1).

2. Sums Involving the Gamma Function:

   • Theorem 3.3 provides a general formula for sums with a parameter $\mu$:
     $$\sum_{k=0}^n \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{(n+k)(2k+2\mu)} = \frac{(-1)^n}{4^n} \left( \frac{\Gamma^2(\mu)}{\Gamma(\mu+n+1)\Gamma(\mu-n)} - \dots \right)$$
   • This leads to specific rational results for integer and half-integer values of $\mu$ (Corollary 3.4), such as:
     $$\sum_{k=0}^n \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{(n+k)(2k+1)} = \frac{2}{(2n-1)(2n+1)}$$

3. Sums with Squared Denominators:

   • By integrating with $\ln(1/x)$, the authors derive results for sums involving $(k+1)^2$ (Theorem 3.7 and Corollary 3.8).
   • Example: $\sum_{k=0}^n \binom{n+k}{2k} \binom{2k}{k} \frac{(-1)^k}{(n+k)(k+1)^2} = \frac{1}{(n-1)n(n+1)}$ for $n \geq 2$.

4. Sums Involving Central Binomial Coefficients Squared:

   • Theorem 3.10 presents complex identities involving the square of central binomial coefficients $\binom{2k}{k}^2$ and the function $\arcsin(x)$. These results connect the sums to specific values involving $\pi$ and powers of 2, such as:
     $$\sum_{k=0}^{2n} \binom{2n+k}{2k} \binom{2k}{k}^2 \frac{2^{-2k}(2k+1)(-1)^k}{(2n+k)(k+1)^2} = \frac{2^{-4n}}{n^3} \binom{2(n-1)}{n-1}^2$$

4. Significance

• Unification of Discrete and Continuous Mathematics: The paper demonstrates a powerful technique for solving discrete combinatorial problems by mapping them onto the continuous domain of orthogonal polynomials. This approach simplifies the derivation of closed forms that would otherwise require complex induction or hypergeometric series manipulation.
• Expansion of Known Results: The authors provide closed forms for sums that were previously either unknown or required case-by-case analysis. The results extend the catalog of known identities in the On-Line Encyclopedia of Integer Sequences (OEIS).
• Utility of Special Functions: The work highlights the utility of the Gamma function and specific integral representations (like those involving $\arcsin$ and $\ln$) in evaluating combinatorial sums, offering a template for future research in analytic combinatorics.
• Educational Value: The paper serves as a clear example of how classical properties of Legendre polynomials (Rodrigues' formula, generating functions, orthogonality) can be applied to modern combinatorial problems.

In summary, Bataille and Frontczak successfully utilize the analytical properties of Legendre polynomials to derive a wide array of new and elegant closed-form solutions for complex combinatorial sums, enriching the field of discrete mathematics with tools from mathematical analysis.