In this post we evaluate the sum . Then we’ll generalize it and evaluate .
The key tools we need for the first sum are the trinomial revision identity, , and the parallel summation identity, . Using trinomial revision, we have
We can evaluate the remaining sum using parallel summation, but we need to pull a variable switch first. Replace k with and then apply parallel summation to obtain
We thus have the identity
where the last step follows thanks to some algebra simplification with factorials.
To evaluate the second sum we’ll need an identity that’s like an upper-index version of Vandermonde’s convolution: . Otherwise, the derivation for the second sum proceeds just as the first one does up through the point where we replace k with . Continuing from there and applying the upper Vandermonde identity, we have
We can rewrite this and perform some more algebra simplification to get our generalization: