Closed form for a binomial identity

Question

$\textrm {How do I find a closed form for } \sum_{j=0}^n{} j\displaystyle\binom{j}{r} = ?$

Is this some kind of upper index summation?

Any previous papers?

Thank you

Answer 1

$$\sum_{n=0}^\infty \binom{n}{r}x^n = \frac{x^r}{(1-x)^{r+1}}$$

Taking the derivative and multiplying by $x$ gives us:

$$\sum_{n=1}^\infty n\binom{n}{r} x^{n} = \frac{x^{r+1}+ rx^{r}}{(1-x)^{r+2}}$$

Multiplying by $\frac{1}{1-x}$, we get:

$$\sum_{n=0}^{\infty}x^n\left(\sum_{j=1}^{n}j\binom{j}{r}\right)=\frac{x^{r+1}+rx^r}{(1-x)^{r+3}}$$

Now, $$\frac{1}{(1-x)^{r+3}}=\sum_{k=0}^\infty \binom{r+k+2}{r+2}x^k$$

So $$\sum_{j=1}^{n}j\binom{j}{r} = \binom{n+1}{r+2} + r\binom{n+2}{r+2}$$

You can, perhaps, prove this directly by induction.

Another more direct approach would use:

$$(j+1)\binom{j}{r}= \frac{(j+1)!}{r!(r-j)!} = (r+1)\binom{j+1}{r+1}$$

Using this and some known formulas, we get that your sum is:

$$(r+1)\binom{n+2}{r+2}-\binom{n+1}{r+2}$$

This is, in fact, equal to my previous expression.

Counting proof

The left side $\sum_{j=1}^{n}j\binom{j}{r}$, counts the number of ways of picking $r+1$ elements of $\{1,2,3,\dots,n+1\}$, and then picking a free number less than the maximum in that set (the free number can be in the $r+1$-subset our not.) $j\binom{j}{r}$ counts the number of such selection where the set's maximum is $j+1$.

Now $(r+1)\binom{n+1}{r+2}$ counts the cases where the free number is chosen outside $r+1$-set - you pick $r+2$ numbers, then pick one of the non-maximum values as the free selection. Also, $r\binom{n+1}{r+1}$ counts the number of ways of picking the $r+1$ elements and then picking the free number as one of the $r$(non-maximal) elements of that set.

So: $$\sum_{j=1}^{n}j\binom{j}{r} = (r+1)\binom{n+1}{r+2}+r\binom{n+1}{r+1}$$

Again, using simple manipulation, you can see this is the same.