[width=0.8]figures/warehouse.png

Figure : Qualitative results from the execution of plans generated by solving
the package rearrangement problems in Tasks 1-5 with GTPMIP

##  1 Methodology

In this section, we describe each component of our approach, as illustrated in
Figure LABEL:fig:overview. We name our approach Grounded Task Planning as
Mixed Integer Programming (GTPMIP). As stated in the previous section, GTPMIP
takes as input a description of the optimal constrained task planning problem
including descriptions of action primitives the robot is capable of executing.
GTPMIP then builds a Hybrid Funnel Graph from this description to represent
the entire plan space. Finally, it encodes the Hybrid Funnel Graph and the
planning problem as an MICP, which it then solves using an off-the-shelf MIP
solver. Each of these components are described in the following subsections.

###  Hybrid PDDL Description

Hybrid PDDL Description (HPD) is an extension of PDDL that allows for the
specification of task planning problems with numerical action and task
constraints, numerical initial values of continuous task variables, numerical
objective functions, numerical action dynamics functions, numerical
preconditions and numerical effects. Similar to PDDL, an HPD description of a
task planning problem is made up of two files; the domain.hpd file and the
problem.hpd file. The domain.hpd file describes the action primitives that the
robot can execute. An action primitive has fields

  * •

:action to specify the name of the action primitive

  * •

:parameters to specify the symbolic and continuous parameters the action
takes.

  * •

:precondition to specify a conjunction of symbols whose truth-values must be
true in order for the action to be executable.

  * •

:continuous_precondition to specify continuous constraints on the continuous
variables that must be satisfied in order for the action to be executable.

  * •

:dynamics to specify dynamics functions that compute the state of the
continuous variables after the action is executed.

  * •

:continuous_effect to specify the numerical values of continuous variables
after the action is executed.

  * •

:effect to specify a conjunction of symbols that represent the state of the
world after the action is executed.

The problem.hpd file describes the initial symbolic and continuous states as
well as the goal symbolic and continuous states of the task. It also describes
the task-specific constraints and the objective function to be optimized.
PDDL+, which is also an extension to PDDL, allows for the specification of
numerical action effects. However, unlike HPD, PDDL+ is incapable of
specifying numerical task constraints, objective functions and action dynamics
functions.

###  Funnels and Hybrid Funnel Graphs

We represent action primitives as funnels. A funnel is made up of three
components; an input region, a dynamics function and an output region. The
input region is the region of intersection of all the continuous constraints
that need to be satisfied before the action can be executed (the continuous
preconditions). The dynamics function computes the state of the continuous
variables after the action is executed. We apply the dynamics function on the
peripheries of the input region to result in a new region which we call the
output region. The geometric representation of this abstraction takes the
shape of a funnel as shown in Figure 1; hence its name. The representation of
action primitives as funnels helps in determining which action primitives are
applicable given the state of the robot. If the values of the continuous
variables of the current state intersects with the input region of a funnel
and the symbolic preconditions of the corresponding action hold true for the
symbolic propositions of current state, then the action is applicable. The
output region of the funnel also determines the continuous state after the
corresponding action is executed. In addition to action funnels, No-op funnels
are identity operations which represent actions that make no changes to the
symbolic state of the world and whose set of symbolic preconditions are equal
to their set of symbolic effects. Given this representation of actions as
funnels, we build up the Hybrid Funnel Graph by alternating between state
levels and action levels. A state level is a set of all possible states (both
symbolic and continuous) at a specific time instance. An action level is a set
of all applicable funnels at a specific time instance. The first state level
is a set of all the symbolic propositions $\mathcal{I}$ and continuous
variables $\mathcal{X}^{I}_{b}$ where $\mathcal{X}^{I}_{r}$ that make up the
initial state. The continuous variables could take the form of either singular
continuous values or intervals of continuous values that represent regions in
the continuous space (SE(2) space in our package rearrangement problem
formulation). We then compute all funnels that are applicable given the
symbolic and continuous state variables in the first state level. These
funnels constitute the first action level. As noted in the previous paragraph,
a funnel is applicable to a state level if the continuous state variables in
the state level intersect with the input region of the funnel and the symbolic
preconditions of the action corresponding to the funnel hold true for the
symbolic propositions of the state level. We also include to the first action
level, No-op funnels for each symbolic proposition in the state level. The
second state level is then computed as the set of all symbolic effects of
actions and output regions of their corresponding funnels in the first action
level. These output regions are computed by applying the funnel’s dynamics
function to the region of intersection of the continuous variables of the
first state level and the funnel’s input region. Likewise, the second action
level is computed in the same manner as the first action level. After the
computation of each state level, we check if the goal symbolic propositions
$\mathcal{G}$ hold true in the state level and if the goal continuous variable
values $\mathcal{X}^{G}_{b}$ where $\mathcal{X}^{G}_{r}$ intersect the
continuous variable regions in the state level. If both of these conditions
are true, we have a valid Hybrid Funnel Graph for the task and terminate the
graph building process. If not, we keep building the graph by adding
additional state and action levels. Each action level represents a single time
step in the resulting plan. Hence the total number of action levels, $T$,
represents the total period of the entire resulting plan. Note that, since the
Hybrid Funnel Graph starts with the initial state level and ends with the
terminal state level, the total number of state levels is greater than the
total number of action levels, $T$, by 1. This process is similar to the
process of building planning graphs in GraphPlan [graphplan] except that
planning graphs in GraphPlan are made up of only symbolic propositions and
symbolic actions. Hybrid Funnel Graphs are made up of both symbolic
propositions and continuous variables, hence its name. Unlike with GraphPlan
where the graph building process is guaranteed to terminate if the planning
problem is valid, our approach to building Hybrid Funnel Graphs is not
guaranteed to terminate due to our inclusion of continuous variables. However
in this work we observe GTPMIP successfully terminate graph building in every
planning problem it is applied to.

[width=0.45]figures/funnel.png

Figure : A funnel representation for the move action. The input region is
formed by the intersection of continuous precondition inequality constraints
($g_{1}~{}\text{to}~{}g_{4})$ on the robot position. The action dynamics
compute the next robot position, $x_{t+1},y_{t+1}$ after the action is applied
to the poses in the input region. The output region represents the space of
resulting poses.

###  Encoding as a Mixed Integer Convex Program

Before we encode the Hybrid Funnel Graph and the planning problem as an MICP,
we first define a set of useful variables.

  * •

Let $T$ represent the total number of action levels in our Hybrid Funnel
Graph, which is also the total planning period.

  * •

Let $\mathcal{F}$ represent the set of all instantiated symbolic propositions
in our planning domain. Hence $\mathcal{I}\subseteq\mathcal{F}$ and
$\mathcal{G}\subseteq\mathcal{F}$

  * •

Let $\mathcal{A}$ represent the set of all instantiated actions in our
planning domain.

  * •

Let $\text{pre}_{f}$ represent the set of all actions that have symbolic
proposition $f$ as a symbolic precondition.

  * •

Let $\text{add}_{f}$ represent the set of all actions whose symbolic effects
affirm symbolic proposition $f$. (the truth-value of $f$ in the action’s
symbolic effect is True).

  * •

Let $\text{del}_{f}$ represent the set of all actions whose symbolic effects
negate symbolic proposition $f$. (the truth-value of $f$ in the action’s
symbolic effect is False)

Next, we define integer variables. For all $f\in\mathcal{F}$ and $t\in 1\dots
T$,

$p_{f,t}=\cases{1},&\text{ifproposition}f\text{holdstrueattime}t\\\
0,\text{otherwise}$
$q_{a,t}=\cases{1},&\text{ifaction}a\text{istakenattime}t\\\
0,\text{otherwise}$

Given these variable definitions, we now build the constraints into our MICP.
The first set of constraints to be added are the initial and terminal
constraints. The initial constraint,

$p_{f,1}=\cases{1},&\forall f\in\mathcal{I}\\\ 0,\forall f\notin\mathcal{I}$
(1)

ensures that all initial symbolic propositions hold true in the first state
level. The terminal constraint,

$p_{f,T+1}=1,~{}~{}\forall f\in\mathcal{G}$ (2)

ensures that all goal symbolic propositions hold true in the last state level.
The next set of constraints are the precondition constraints

$q_{a,t}\leq p_{f,t},~{}~{}\forall a\in\text{pre}_{f},\forall t\in 1\dots
T,f\in\mathcal{F}$ (3)

These inequality constraints encode the implication constraint that if action
$a$, which has symbolic proposition $f$ as its precondition, is taken in
action level $t$, then $f$ should also hold true in state level $t$. This
constraint is called the precondition constraint because it ensures that all
preconditions of an action hold true before the action can be taken. The next
set of constraints are the effect constraints

$p_{f,t+1}\leq\sum_{a\in\text{add}_{f}}q_{a,t},~{}~{}\forall t\in 1\dots
T,f\in\mathcal{F}$ (4)

These inequality constraints encode the implication constraint that if
symbolic proposition $f$ holds true in state level $t+1$, then at least one
action $a$ which has $f$ as a positive effect should be taken in action level
$t$. The next set of constraints are the mutual exclusion constraints

$q_{a,t}+q_{a^{\prime},t}\leq 1$ (5)

for all $t\in 1\dots T$ and all $a,a^{\prime}$ for which there exists an
$f\in\mathcal{F}$ such that $a\in\text{del}_{f}$ and
$a^{\prime}\in\text{pre}_{f}\cup\text{add}_{f}$.
These inequality constraints ensure that two actions $a$ and $a^{\prime}$ that
cancel each other are not both taken in action level $t$. The next set of
constraints are the task-specific numerical constraints

$q_{a,t}\leq h(\mathcal{X}^{t}_{r},\mathcal{X}^{t}_{b}),~{}~{}\forall
h\in\mathcal{H},t\in 1\dots T$ (6)

that ensure that if action $a$ is taken in action level $t$, the continuous
variable parameters of $a$ satisfy all the task-specific numerical constraints
$\mathcal{H}$. The final set of constraints are the initial and terminal
constraints

$\split\mathcal{X}^{1}_{r}=\mathcal{X}^{I}_{r},~{}~{}\mathcal{X}^{1}_{b}=\mathcal{X}^{I}_{b}$
(7)

and

$\split\mathcal{X}^{T+1}_{r}=\mathcal{X}^{G}_{r},~{}~{}\mathcal{X}^{T+1}_{b}=\mathcal{X}^{G}_{b}$
(8)

that ensure that the values of continuous variables at the first and final
levels are equal to the problem-specified initial and goal continuous variable
values respectively. The objective function to be optimized

$J(\mathcal{X}^{t}_{r},\mathcal{X}^{t}_{b})~{}~{}\forall t\in 1\dots T$ (9)

is a convex function on all continuous variables for the entire planning
period. For a warehouseman’s problem, a suitable objective function would be
to minimize the total Euclidean distance the robot travels while rearranging
the packages. Putting together Equations 1 - 9, our entire MICP can now be
summarized as

$\split\min_{\mathcal{X}^{t}_{r},\mathcal{X}^{t}_{b},q_{a,t}}J(\mathcal{X}^{t}_{r},\mathcal{X}^{t}_{b}),~{}~{}\forall
t\in 1\dots T\\\ \text{subjectto\quad\quad\quad\quad\quad\quad\quad\quad}\\\
p_{f,1}=\cases{1},&\forall f\in\mathcal{I}\\\ 0,\forall f\notin\mathcal{I}\\\
p_{f,T+1}=1,~{}~{}\forall f\in\mathcal{G}\\\ q_{a,t}\leq p_{f,t},~{}~{}\forall
a\in\text{pre}_{f},~{}~{}\forall t\in 1\dots T,f\in\mathcal{F}\\\
p_{f,t+1}\leq\sum_{a\in\text{add}_{f}}q_{a,t},~{}~{}\forall t\in 1\dots
T,f\in\mathcal{F}\\\ q_{a,t}+q_{a^{\prime},t}\leq 1\\\ q_{a,t}\leq
h(\mathcal{X}^{t}_{r},\mathcal{X}^{t}_{b}),~{}~{}\forall h\in\mathcal{H},t\in
1\dots T\\\
\mathcal{X}^{1}_{r}=\mathcal{X}^{I}_{r},~{}~{}\mathcal{X}^{1}_{b}=\mathcal{X}^{I}_{b}\\\
\mathcal{X}^{T+1}_{r}=\mathcal{X}^{G}_{r},~{}~{}\mathcal{X}^{T+1}_{b}=\mathcal{X}^{G}_{b}\\\
p\in\\{0,1\\},q\in\\{0,1\\},\mathcal{X}\in\text{SE(2)}\\\ $ (10)

We solve this MICP using an off-the-shelf MIP solver which returns the
grounded plan $\pi^{*}$ made up of a sequence of logically consistent actions
$\\{a_{1}(\mathcal{X}^{1*}_{r},\mathcal{X}^{1*}_{b}),a_{2}(\mathcal{X}^{2*}_{r},\mathcal{X}^{2*}_{b}),\dots,a_{T}(\mathcal{X}^{T*}_{r},\mathcal{X}^{T*}_{b})\\}$,
with each action associated with its corresponding optimal continuous
parameter values.


# On some Binomial Coefficient Identities with Applications

necdet batır  department of mathematics, nevşehir hbv university, nevşehir,
50300 turkey<EMAIL_ADDRESS>,  Sezer Sorgun  department of mathematics,
nevşehir hbv university, nevşehir, 50300 turkey<EMAIL_ADDRESS>and  Sevda
Atpınar  department of mathematics, nevşehir hbv university, nevşehir, 50300
turkey<EMAIL_ADDRESS>
###### Abstract.

We present a different proof of the following identity due to Munarini, which
generalizes a curious binomial identity of Simons.

$\displaystyle\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}x^{k}$
$\displaystyle=\sum_{k=0}^{n}(-1)^{n+k}\binom{\beta-\alpha+n}{n-k}\binom{\beta+k}{k}(x+1)^{k},$

where $n$ is a non-negative integer and $\alpha$ and $\beta$ are complex
numbers, which are not negative integers. Our approach is based on a
particularly interesting combination of the Taylor theorem and the Wilf-
Zeilberger algorithm. We also generalize a combinatorial identity due to Alzer
and Kouba, and offer a new binomial sum identity. Furthermore, as
applications, we give many harmonic number sum identities. As examples, we
prove that

$H_{n}=\frac{1}{2}\sum_{k=1}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}H_{k}$

and

$\displaystyle\sum_{k=0}^{n}\binom{n}{k}^{2}H_{k}H_{n-k}=\binom{2n}{n}\left((H_{2n}-2H_{n})^{2}+H_{n}^{(2)}-H_{2n}^{(2)}\right).$

###### Key words and phrases:

combinatorial identity, binomial coefficient, harmonic number, harmonic sum,
Legendre polynomial

###### 2000 Mathematics Subject Classification:

Primary 05A10; Secondary 05A19

##  1\. Introduction

In 2001 Simons [12] discovered a curious binomial identity which can be
equivalently written as

(1.1)
$\sum_{k=0}^{n}\binom{n}{k}\binom{n+k}{k}x^{k}=\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}(x+1)^{k}.$

This formula has attracted the attention of several researchers and many
alternative proofs of it have appeared in the literature. These authors used a
variety of techniques in their proofs. For instance, Batır and Atpınar [4]
extended (1.1) using the Taylor theorem. Chapman [5], using the generating
function method, gave an elegant and short proof of (1.1). Prodinger [10] used
the Cauchy integral formula to demonstrate a novel and very short proof of
this identity. Wang and Sun [15] presented a very short proof of it utilizing
a linear transformation in the space of polynomials. Shattuck [11] presented
combinatorial proofs of some Simons-type binomial coefficient identities.
Hirschhorn [7] made short comments on Simons’ curious identity. Also, see some
recent studies given by Wei et al. [16] and Xu and Cen [14]. Munarini [8],
using the Cauchy integral formula, offered the following nice generalization
of (1.1):

$\displaystyle\sum_{k=0}^{n}\binom{\alpha}{n-k}$
$\displaystyle\binom{\beta+k}{k}x^{k}y^{n-k}$ (1.2)
$\displaystyle=\sum_{k=0}^{n}(-1)^{n+k}\binom{\beta-\alpha+n}{n-k}\binom{\beta+k}{k}(x+y)^{k}y^{n-k}.$

This can be rewritten as follows after replacing $x$ by $\frac{x}{y}$.

(1.3)
$\displaystyle\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}x^{k}=\sum_{k=0}^{n}(-1)^{n+k}\binom{\beta-\alpha+n}{n-k}\binom{\beta+k}{k}(x+1)^{k}.$

Note that (1) reduces to (1.1) when we put $\alpha=\beta=n$ and $y=1$. Our
first aim in the paper is to provide a different proof of (1) using the Taylor
theorem and the Wilf-Zeilberger algorithm; see [9].

In a recent paper [1, Eq. (4.1)]), Alzer and Kouba proved the following
identity

(1.4)
$4^{n}\binom{\lambda}{n}=\binom{2\lambda}{n}\sum_{k=0}^{n}\binom{n}{k}\frac{\binom{n-\lambda-1/2}{k}}{\binom{k-\lambda-1/2}{k}},$

which is valid for all integers $n\geq 0$ and any complex number $\lambda$,
and they used it to derive several harmonic number sum identities. The second
aim of this work is to generalize identity (1.4) and to apply it to deduce
further binomial sum identities involving harmonic numbers. Our final aim is
to prove a new binomial sum identity, which is stated in Theorem 2.2. The
proofs of Theorems 2.2 and 2.3 are relied on the WZ theory. Applications of
our results lead to many interesting and new combinatorial identities
involving harmonic numbers. We also give a new representation for the Legendre
polynomials $P_{n}(x)$. Many examples of these kinds obtained by taking
particular values of the parameters involved are collected in Section 3. To
ensure accuracy, all formulas appearing in this paper were verified
numerically by Mathematica. We believe that the method we used in the proofs
of the theorems can be applied to prove some other combinatorial equalities.

Now we need to recall some basic tools that we use to prove our examples. The
classical gamma function $\Gamma(x)=\int_{0}^{\infty}u^{x-1}e^{-u}du$ and the
digamma function $\psi$, logarithmic derivative of the $\Gamma$-function
satisfy the following relations for any integer $n\geq 0$

(1.5) $\Gamma\left(n+\frac{1}{2}\right)=\frac{(2n)!\Gamma(1/2)}{2^{2n}n!},$

and for any complex number $x$, which is not an integer

(1.6) $\Gamma(x)\Gamma(1-x)=\frac{\pi}{\sin(\pi x)},$ (1.7)
$\psi(n+1/2)-\psi(1/2)=2H_{2n}-H_{n},$

where $\gamma=0.57721...$ is the Euler-Mascheroni constant and
$H_{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ is $n$ th harmonic
number, and

(1.8) $\psi(1-x)-\psi(x)=\pi\cot(\pi
x)\quad\mbox{and}\quad\psi^{\prime}\left(x\right)-\psi^{\prime}\left(1-x\right)=\pi^{2}\csc^{2}(\pi
x);$

see, for example, [13]. A generalized binomial coefficient $\binom{s}{t}$ is
defined, in terms of the classical gamma function, by

(1.9) $\binom{s}{t}=\frac{\Gamma(s+1)}{\Gamma(t+1)\Gamma(s-t+1)},\quad
s,t\in\mathbb{C}.$

##  2\. Main Results

In the first theorem in this section we give a different proof of (1.3) using
the Taylor theorem and the WZ theory.

######  Theorem 2.1.

For all $\alpha,\beta\in\mathbb{C}$, which are not negative integers, and any
non-negative integer $n$ we have

(2.1)
$\displaystyle\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}x^{k}=\sum_{j=0}^{n}(-1)^{n+j}\binom{\beta-\alpha+n}{n-j}\binom{\beta+j}{j}(x+1)^{j}.$

###### Proof.

We define

(2.2) $\displaystyle
f(x)=\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}x^{k}.$

Since $f$ is a polynomial of degree $n$ in $x$ its Taylor polynomial at $x=-1$
is

(2.3) $f(x)=\sum_{j=0}^{n}\frac{f^{(j)}(-1)}{j!}(x+1)^{j}.$

Differentiating $f$ $j$ times it follows that

$\displaystyle\frac{f^{(j)}(x)}{j!}=\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}\binom{k}{j}x^{k-j}.$

We set $x=-1$ and get

$\displaystyle\frac{f^{(j)}(-1)}{j!}=\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}\binom{k}{j}(-1)^{k-j}.$

Applying this to (2.3) yields

$f(x)=\sum_{j=0}^{n}\left(\sum_{k=0}^{n}\binom{\alpha}{n-k}\binom{\beta+k}{k}\binom{k}{j}(-1)^{k-j}\right)(x+1)^{j}.$

Comparing the coefficients of $(x+1)^{j}$ in this identity and the right-hand
side of (2.1) we conclude that (2.1) holds if and only if for all
$\alpha,\beta\in\mathbb{C}$, which are not negative integers, and all
$j=0,1,2,...,n$ we have

(2.4)
$\sum_{k=0}^{n}(-1)^{k+j}\binom{\beta+k}{k}\binom{k}{j}\binom{\alpha}{n-k}=(-1)^{n+j}\binom{\beta+j}{j}\binom{\beta-\alpha+n}{n-j}.$

In order to show that (2.4) is valid we define

(2.5)
$F(n,k)=\frac{(-1)^{k+n}\binom{\beta+k}{k}\binom{k}{j}\binom{\alpha}{n-k}}{\binom{\beta+j}{j}\binom{-\alpha+\beta+n}{n-j}}.$

Applying the Wilf-Zeilberger algorithm [9], we find the companion function

(2.6)
$G(n,k)=\frac{(-1)^{n+k}(j-k)(\alpha+k-n)\binom{\beta+k}{k}\binom{k}{j}\binom{\alpha}{n-k}}{(k-n-1)(\alpha-\beta-n-1)\binom{\beta+j}{j}\binom{-\alpha+\beta+n}{n-j}}$

and the following difference equation holds

$F(n,k)-F(n+1,k)=G(n,k+1)-G(n,k).$

We sum both sides of this equation from $k=0$ to $k=n+1$ and get

$\sum_{k=0}^{n+1}\big{(}F(n,k)-F(n+1,k)\big{)}=\sum_{k=0}^{n+1}\big{(}G(n,k+1)-G(n,k)\big{)}.$

The right hand side of this equality is a telescoping sum, thus

$\sum_{k=0}^{n+1}F(n,k)-\sum_{k=0}^{n+1}F(n+1,k)=G(n,n+2)-G(n,0).$

It is obvious from (15) that $G(n,0)=G(n,n+2)=0$. Note that
$\binom{\alpha}{-2}=0$. This leads to

$\sum_{k=0}^{n+1}F(n,k)-\sum_{k=0}^{n+1}F(n+1,k)=0.$

or equivalently

$\sum_{k=0}^{n+1}F(n+1,k)-\sum_{k=0}^{n}F(n,k)-F(n,n+1)=0.$

But since $F(n,n+1)=0$, which follows from (2.5), this gives

$\sum_{k=0}^{n+1}F(n+1,k)-\sum_{k=0}^{n}F(n,k)=0.$

Replacing $n$ by $\upsilon$ here and then summing the resultant identity from
$\upsilon=0$ to $\upsilon=n-1$ we conclude

$\sum_{\upsilon=0}^{n-1}\bigg{(}\sum_{k=0}^{\upsilon+1}F(\upsilon+1,k)-\sum_{k=0}^{\upsilon}F(\upsilon,k)\bigg{)}=0.$

This is also a telescoping sum, thus, we obtain

$\sum_{k=0}^{n}F(n,k)-F(0,0)=0.$

Since $0\leq j\leq n$ we have from (2.5) that $F(0,0)=1$, so that

$\sum_{k=0}^{n}F(n,k)=1,$

which is equivalent to (2.4). This completes the proof of Theorem 2.1. ∎

In the next theorem, we generalize the identity given by (1.4).

######  Theorem 2.2.

Let $s$ and $t$ be complex numbers, which are not negative integers and $n$ be
a non-negative integer. Then we have

(2.7)
$\sum_{k=0}^{n}\binom{n}{k}\frac{\binom{s}{k}}{\binom{t+k}{k}}=\frac{\binom{n+s+t}{s}}{\binom{s+t}{s}}.$

###### Proof.

Our proof is based on the Wilf-Zeilberger algorithm. Let

(2.8)
$A(n,k)=\frac{\binom{n}{k}\binom{s}{k}\binom{s+t}{t}}{\binom{t+k}{k}\binom{n+s+t}{s}}.$

In order to complete the proof it suffices to show that

$\sum_{k=0}^{n}A(n,k)=1.$

The Wilf–Zeilberger algorithm gives us

(2.9)
$B(n,k)=\frac{k(t+k)\binom{n}{k}\binom{s}{k}\binom{t+s}{t}}{(k-n-1)(n+t+s+1)\binom{t+k}{k}\binom{n+s+t}{s}}$

and the pair $(A,B)$ is a WZ-pair. That is,

$A(n+1,k)-A(n,k)=B(n,k+1)-B(n,k).$

We sum both sides of this equation from $k=0$ to $k=n+1$. This gives us

$\sum_{k=0}^{n+1}\big{(}A(n+1,k)-A(n,k)\big{)}=\sum_{k=0}^{n+1}\big{(}B(n,k+1)-B(n,k)\big{)}.$

The right hand side of this equality is a telescoping sum, thus

$\sum_{k=0}^{n+1}A(n+1,k)-\sum_{k=0}^{n+1}A(n,k)=B(n,n+2)-B(n,0).$

It is obvious from (2.9) that $B(n,0)=B(n,n+2)=0$. This leads to

$\sum_{k=0}^{n+1}A(n+1,k)-\sum_{k=0}^{n+1}A(n,k)=0.$

or equivalently

$\sum_{k=0}^{n+1}A(n+1,k)-\sum_{k=0}^{n}A(n,k)-A(n,n+1)=0.$

But since $A(n,n+1)=0$, which follows from (2.8), it follows that

$\sum_{k=0}^{n+1}A(n+1,k)-\sum_{k=0}^{n}A(n,k)=0.$

Replacing $n$ by $p$ here and then summing the resultant identity from $p=0$
to $p=n-1$ we arrive at

$\sum_{p=0}^{n-1}\bigg{(}\sum_{k=0}^{p+1}A(p+1,k)-\sum_{k=0}^{p}A(p,k)\bigg{)}=0.$

This is also a telescoping sum, thus, we obtain

$\sum_{k=0}^{n}A(n,k)-A(0,0)=0.$

By (2.8) we have $A(0,0)=1$, so that

$\sum_{k=0}^{n}A(n,k)=1,$

completing the proof of Theorem 2.2. ∎

Note that (2.7) reduces to (1.4) when we substitute $s=n-\lambda-\frac{1}{2}$
and $t=-\lambda-\frac{1}{2}$.

######  Theorem 2.3.

Let $s$ and $p$ be complex numbers, which are not negative integers, and $n$
be a non-negative integer. Then we have

(2.10)
$\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{s+k}{k}\binom{k}{p}=\binom{n}{p}\binom{s+p}{n}.$

###### Proof.

We again employ the WZ theory. Let

(2.11)
$P(n,k)=\frac{(-1)^{n+k}\binom{n}{k}\binom{s+k}{k}\binom{k}{p}}{\binom{n}{p}\binom{s+p}{n}}.$

Using the Wilf-Zeilberger algorithm, this gives us the companion function

(2.12)
$Q(n,k)=\frac{(-1)^{n+k}k(k-p)\binom{n}{k}\binom{k}{p}\binom{-1-s}{k}}{(-1+k-n)(n-p-s)\binom{n}{p}\binom{s+p}{n}},$

and we obtain that the pair $(P,Q)$ satisfies the following difference
equation

$P(n,k)-P(n+1,k)=Q(n,k+1)-Q(n,k).$

We sum both sides of this equation from $k=0$ to $k=n+1$ and get

$\sum_{k=0}^{n+1}\big{(}P(n,k)-P(n+1,k)\big{)}=\sum_{k=0}^{n+1}\big{(}Q(n,k+1)-Q(n,k)\big{)}.$

The right hand side of this equality is a telescoping sum, so that

$\sum_{k=0}^{n+1}P(n,k)-\sum_{k=0}^{n+1}P(n+1,k)=Q(n,n+2)-Q(n,0).$

It is clear from (2.12) that $Q(n,0)=Q(n,n+2)=0$. This leads to

$\sum_{k=0}^{n+1}P(n,k)-\sum_{k=0}^{n+1}P(n+1,k)=0$

or equivalently

$\sum_{k=0}^{n+1}P(n+1,k)-\sum_{k=0}^{n}P(n,k)-P(n,n+1)=0.$

But since $P(n,n+1)=0$, which follows from (2.11), this gives

$\sum_{k=0}^{n+1}P(n+1,k)-\sum_{k=0}^{n}P(n,k)=0.$

Replacing $n$ by $p$ here and then summing the resultant identity from $p=0$
to $p=n-1$ we obtain

$\sum_{p=0}^{n-1}\bigg{(}\sum_{k=0}^{p+1}P(p+1,k)-\sum_{k=0}^{p}P(p,k)\bigg{)}=0.$

This is also a telescoping sum, thus, we have

$\sum_{k=0}^{n}P(n,k)-P(0,0)=0.$

By (2.11) we have $P(0,0)=1$, so that

$\sum_{k=0}^{n}P(n,k)=1,$

which is equivalent to (2.10). ∎

##  3\. Applications

In this section we provide many applications of Theorems 2.1, 2.2 and 2.3 by
setting particular values for the paremeters $\alpha,\,\beta$, $t$, $s$ and
$p$. It seems to us that all examples offered here are new in the literature.
If we set $\alpha=n$ in (2.1) and use

$\binom{\beta}{n-k}\binom{\beta+k}{k}=\binom{n}{k}\binom{\beta+k}{n},$

which can be easily verified, we get

(3.1)
$\sum_{k=0}^{n}\binom{n}{k}\binom{\beta+k}{k}x^{k}=\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{\beta+k}{n}(1+x)^{k},$

where $\beta$ and $x$ are complex numbers with $\beta\neq-1,-2,-3,...$ and
$n\geq 0$ be an integer.
$\bullet$ We set $x=0$ and $x=-1$ in (3.1) and get, respectively

(3.2) $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{\beta+k}{n}=(-1)^{n}$

and

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{\beta+k}{k}=(-1)^{n}\binom{\beta}{n}.$

$\bullet$ Differentiate both sides of (3.1) with respect to $\beta$ and then
put $\beta=n$ to obtain

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{n+k}{k}H_{n+k}-H_{n}\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{n+k}{k}=(-1)^{n}H_{n}.$

Using (3.2) with $\beta=n$, this gives the following explicit representation
for $H_{n}$.

$H_{n}=\frac{1}{2}\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}H_{n+k}.$

$\bullet$ Substituting $\beta=-\frac{1}{2}$ in (3.1) produces

(3.3)
$\sum_{k=0}^{n}\binom{n}{k}\binom{-\frac{1}{2}+k}{k}x^{k}=\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{-\frac{1}{2}+k}{n}(1+x)^{k}.$

We have

$\binom{-1/2+k}{k}=\frac{\Gamma(k+1/2)}{k!\Gamma(1/2)}=\frac{1}{4^{k}}\binom{2k}{k}$

and

$\binom{-1/2+k}{n}=\frac{\Gamma(k+1/2)}{n!\Gamma(1/2+k-n)}=\frac{(-1)^{n+k}\binom{2k}{k}\binom{2n-2k}{n-k}}{4^{n}\binom{n}{k}},$

both of which follow from the Legendre’s duplication and reflection formulas
for the classical gamma function $\Gamma$ given in (1.5), (1.6) and (1.7).
Replacing these in (3.3) it follows that

(3.4)
$\sum_{k=0}^{n}\binom{n}{k}\binom{2k}{k}\frac{x^{k}}{2^{2k}}=\frac{1}{2^{2n}}\sum_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}(1+x)^{k}.$

$\bullet$ Let $P_{n}(x)$ be the classical Legendre’s polynomials. From [6, p.
39] (see also [1]) we have

$t^{n}P_{n}\left(\frac{t^{2}+1}{2t}\right)=\frac{1}{4^{n}}\sum_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}t^{2k}.$

Making the substitution $x\to t^{2}-1$ in (3.4), we have

$\sum_{k=0}^{n}\binom{n}{k}\binom{2k}{k}\left(\frac{t^{2}-1}{4}\right)^{k}=\frac{1}{4^{n}}\sum_{k=0}^{n}\binom{2k}{k}\binom{2n-2k}{n-k}t^{2k}.$

From the last two identities we deduce the following new representation for
the Legendre’s polynomials for $t\neq 0$:

$P_{n}\left(\frac{t^{2}+1}{2t}\right)=\frac{1}{t^{n}}\sum_{k=0}^{n}\binom{n}{k}\binom{2k}{k}\left(\frac{t^{2}-1}{4}\right)^{k}.$

By the well-known binomial inversion formula this leads to

$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}P_{k}\left(\frac{t^{2}+1}{2t}\right)t^{k}=\binom{2n}{n}\left(\frac{1-t^{2}}{4}\right)^{n}.$

$\bullet$ Differentiating both sides of (2.10) with respect to $p$ and then
setting $p=0$, we get

(3.5)
$\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{s+k}{k}H_{k}=\binom{s}{n}\big{(}H_{n}+\psi(s+1)-\psi(s-n+1)\big{)}.$

For $s=n$ this leads to the following elegant representation for $H_{n}$:

$H_{n}=\frac{1}{2}\sum_{k=1}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}H_{k},$

where we have used $\psi(n+1)+\gamma=H_{n}$. Setting $s=\frac{1}{2}$ in (3.5)
we get

$\sum_{k=1}^{n}(-1)^{k}\binom{n}{k}\binom{2k}{k}\frac{H_{k}}{4^{k}}=\frac{1}{2^{2n-1}}\binom{2n}{n}\big{(}H_{n}-H_{2n}\big{)}.$

$\bullet$ Differentiating twice both sides of (2.10) with respect to $p$ and
then setting $p=0$ we find that

$\displaystyle\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{s+k}{k}\big{(}H_{k}^{2}+H_{n}^{(2)}\big{)}$
$\displaystyle=\binom{s}{n}\bigg{(}2H_{n}\big{(}\psi(s+1)-\psi(-n+s+1)\big{)}+\psi(-n+s+1)^{2}$
$\displaystyle-2\psi(s+1)\psi(-n+s+1)-\psi^{\prime}(-n+s+1)+H_{n}^{2}$
$\displaystyle+H_{n}^{(2)}+\psi(s+1)^{2}+\psi^{\prime}(s+1)-\psi^{\prime}(s-n+1)\bigg{)}$

where $\psi$ is the digamma function. For $s=n$ this gives

$\displaystyle
H_{n}^{2}=\frac{1}{4}\sum_{k=0}^{n}(-1)^{n+k}\binom{n}{k}\binom{n+k}{k}\big{(}H_{k}^{2}+H_{k}^{(2)}\big{)},$

where $H_{k}^{(2)}=1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{k^{2}}$.
$\bullet$ Applying the binomial inversion formula to (2.10) we get

$\sum_{k=0}^{n}\binom{n}{k}\binom{s+p}{k}\binom{k}{p}=\binom{n}{p}\binom{s+n}{n}.$

Setting $s=n-\frac{1}{2}$ and $p=\frac{1}{2}$ here we obtain

(3.6)
$\sum_{k=0}^{n}\frac{4^{k}\binom{n}{k}^{2}}{\binom{2k}{k}}=\frac{\binom{4n}{2n}}{\binom{2n}{n}}.$

Using

$\binom{2n}{n}\binom{n}{k}^{2}=\binom{2k}{k}\binom{2n-2k}{n-k}\binom{2n}{2k}$

(3.6) can be rewritten in the following elegant form

$\sum_{k=0}^{n}\binom{2n}{2k}\binom{2n-2k}{n-k}4^{k}=\binom{4n}{2n}.$

$\bullet$ Setting $p=n+\frac{1}{2}$ in (2.7) we get

(3.7)
$\sum_{k=0}^{n}\binom{s+k}{k}\binom{2n-2k}{n-k}4^{k}=\frac{\binom{2n}{n}\binom{2n+2s+1}{2s+1}}{\binom{n+s}{n}}.$

If we differentiate both sides of (3.7) with respect to $s$ and then set $s=0$
we conclude that

$\sum_{k=0}^{n}\binom{2k}{k}\frac{H_{n-k}}{4^{k}}=\frac{2n+1}{4^{n}}\binom{2n}{n}\big{(}2H_{2n+1}-H_{n}-2\big{)}.$

$\bullet$ From (2.7) with $s=n$ and $t=1$ we obtain

$\sum_{k=1}^{n}k\binom{n}{k}^{2}=\frac{n}{2}\binom{2n}{n}.$

Applying the operator $\frac{\partial^{2}}{\partial s\partial t}$ both sides
of (2.7), using

$\sum_{k=0}^{n}\binom{n}{k}^{2}H_{k}=\binom{2n}{n}\left(2H_{n}-H_{2n}\right),$

and finally putting $t=0$ and $s=n$ in the resultant we get

$\displaystyle\sum_{k=0}^{n}\binom{n}{k}^{2}H_{k}H_{n-k}$
$\displaystyle=\binom{2n}{n}\left((H_{2n}-2H_{n})^{2}+H_{n}^{(2)}-H_{2n}^{(2)}\right).$

We differentiate both sides of (2.10) with respect to $t$ twice and then we
set $s=n$ and $t=0$. This gives

$\displaystyle\sum_{k=0}^{n}\binom{n}{k}^{2}\left((H_{k})^{2}+H_{k}^{(2)}\right)=\binom{2n}{n}\left((H_{2n}-2H_{n})^{2}+2H_{n}^{(2)}-H_{2n}^{(2)}\right).$

######  Remark 3.1.

It is possible to derive many other examples using our main results, but we
are satisfied with these to keep our paper short. Clearly, the examples
presented here demonstrate the usefulness of our main results. Several other
applications of (3.1) can be found in [4].

## References

  * [1] H. Alzer and O. Kouba, On a combinatorial identity of Gavrea and Ivan and related results, Aequat. Math. 2022, https://doi.org/10.1007/s00010-022-00923-0.
  * [2] N. Batır and A. Sofo, Finite sums involving reciprocals of the binomial and central binomial coefficients and harmonic numbers, Symmetry 13 (11), 2021.
  * [3] N. Batır, H. Küçük, and S. Sorgun, Convolution identities involving the central binomial coefficients and Catalan numbers, Trans. Comb. 10 (2021), 225–238.
  * [4] N. Batır and S. Atpınar, An extension of a curious binomial identity of Simons, Math. Gaz., to appear.
  * [5] R. Chapman, A curious identity revisited, Math. Gaz. 87 (2003), 139–141.
  * [6] H. W. Gould, Combinatorial identities: A standardized set of tables listing 500 binomial coefficient summations by Henry Wadsworth Gould. Morgantown, (1972).
  * [7] M. Hirschhorn, Comments on a curious identity, Math. Gaz. 87 (2003), 528–530.
  * [8] E. Munarini, Generalization of a binomial identity of Simons, Integers: Electron. J. Combin. Number Theory 5 (2005), A15.
  * [9] M. Petkovsek, H. S. Wilf, and D. Zeilberger, A = B, A K Peters Ltd., 1996.
  * [10] H. Prodinger, A curious identity proved by Cauchy integral formula, Math. Gaz. 89 (2005), 266–267.
  * [11] M. Shattuck, Combinatorial proofs of some Simons-type binomial coefficient identities, Integers: Electron. J. Combin. Number Theory 7 (2007), A27.
  * [12] S. Simons, A curious identity, Math. Gaz. 85 (2001), 296–298.
  * [13] H. M. Srivastava and J. Choi, Zeta and $q$-Zeta Functions and Associated Series and Integrals, Elsevier, 2012.
  * [14] A. Xu and Y. Cen, Combinatorial identities from contour integrals, Ramanujan J. 40 (2016), 103–114.
  * [15] X. Wang and Y. Sun, A new proof of a curious identity, Math. Gaz. 91 (2007), 105–106.
  * [16] C. Wei, Y. Wei, and C. Li, Some summation and transformation formulas from inversion techniques, Integers 22 (2022), A95.