How to find a closed form for $\sum_{i=0}^n \binom{a+i}{b+i}i$

Question

Wolframalpha tells me it's $$\frac{b (b + 1) \binom{a + 1}{ b + 1} - (b + n + 1) (b (n + 1) - (a + 1) n) \binom{a + n + 1}{ b + n + 1}}{(a - b + 1) (a - b + 2)}$$ but how to come up with or at least prove that?

Answer 1

This is not quite the same expression, but this is how I would go about finding the closed formula. We can first rewrite the summation as $$\sum_{i=0}^n \binom{a+i}{b+i}i = \sum_{k=1}^n \sum_{i=k}^n \binom{a+i}{b+i}$$ Then we can use the hockey stick formula to get that the inner sum is $$\sum_{k=1}^n \binom{a+n+1}{b+n} - \binom{a + k}{b+k-1}$$ The first term is the same every time, so we can rewrite this as $$n\binom{a+n+1}{b+n} - \sum_{k=1}^n \binom{a+k}{b+k-1}$$ And use the hockey stick formula again to get that this is $$n\binom{a+n+1}{b+n} - \binom{a+n+1}{b+n-1} + \binom{a+1}{b-1}$$ And there we have a closed formula!

Answer 2

By way of enrichment and presenting various techniques we start by introducting

$$S_{a,b}(n) = \sum_{q=0}^n {a+q\choose b+q} q$$

where $a\ge b$ and write with an Iverson bracket

$$\sum_{q\ge 0} {a+q\choose b+q} q [[0\le q\le n]] = \sum_{q\ge 0} {a+q\choose a-b} q [z^n] \frac{z^q}{1-z} \\ = [z^n] \frac{1}{1-z} \sum_{q\ge 0} {a+q\choose a-b} q z^q = [z^n] \frac{1}{1-z} [w^{a-b}] (1+w)^a \sum_{q\ge 0} q z^q (1+w)^q \\ = [z^n] \frac{1}{1-z} [w^{a-b}] (1+w)^a \frac{z(1+w)}{(1-z(1+w))^2} = [z^{n-1}] \frac{1}{1-z} [w^{a-b}] (1+w)^{a+1} \frac{1}{(1-z-zw)^2} = [z^{n-1}] \frac{1}{(1-z)^3} [w^{a-b}] (1+w)^{a+1} \frac{1}{(1-zw/(1-z))^2} \\ = [z^{n-1}] \frac{1}{(1-z)^3} \sum_{q=0}^{a-b} {a+1\choose a-b-q} (q+1) \frac{z^q}{(1-z)^q} \\ = \sum_{q=0}^{a-b} {a+1\choose a-b-q} (q+1) [z^{n-1-q}] \frac{1}{(1-z)^{q+3}} \\ = \sum_{q=0}^{a-b} {a+1\choose a-b-q} (q+1) {n+1\choose q+2} \\ = (n+1) \sum_{q=0}^{a-b} {a+1\choose a-b-q} {n\choose q+1} - \sum_{q=0}^{a-b} {a+1\choose a-b-q} {n+1\choose q+2}.$$

The first sum is

$$\sum_{q=0}^{a-b} {a+1\choose a-b-q} {n\choose q+1} = [z^{a-b}] (1+z)^{a+1} \sum_{q=0}^{a-b} {n\choose q+1} z^q.$$

We may extend $q$ to infinity because of the coefficient extractor in front:

$$[z^{a-b}] (1+z)^{a+1} \sum_{q\ge 0} {n\choose q+1} z^q = [z^{a-b+1}] (1+z)^{a+1} \sum_{q\ge 0} {n\choose q+1} z^{q+1} \\ = [z^{a-b+1}] (1+z)^{a+1} ((1+z)^n - 1) = {n+a+1\choose a-b+1} - {a+1\choose a-b+1}.$$

The second is

$$\sum_{q=0}^{a-b} {a+1\choose a-b-q} {n+1\choose q+2} = [z^{a-b}] (1+z)^{a+1} \sum_{q=0}^{a-b} {n+1\choose q+2} z^q.$$

We may once more extend $q$ to infinity because of the coefficient extractor in front:

$$[z^{a-b}] (1+z)^{a+1} \sum_{q\ge 0} {n+1\choose q+2} z^q = [z^{a-b+2}] (1+z)^{a+1} \sum_{q\ge 0} {n+1\choose q+2} z^{q+2} \\ = [z^{a-b+2}] (1+z)^{a+1} ((1+z)^{n+1} - 1 - (n+1)z) \\ = {n+a+2\choose a-b+2} - {a+1\choose a-b+2} - (n+1) {a+1\choose a-b+1}.$$

Collecting and canceling we obtain at last

$$\bbox[5px,border:2px solid #00A000]{ S_{a,b}(n) = (n+1) {n+a+1\choose a-b+1} - {n+a+2\choose a-b+2} + {a+1\choose a-b+2}}$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ S_{a,b}(n) = (n+1) {n+a+1\choose n+b} - {n+a+2\choose n+b} + {a+1\choose b-1}.}$$

This simplifies to the accepted answer.