# Proving two binomial identities

I would like to show that

\begin{align} &\sum_{j=n-k}^n\binom nj(1-x)^{n-j-1}x^{j-1}(j-nx)\\ &\qquad=\binom n{n-k}(n-k)(1-x)^kx^{n-k-1}\sum_{k=0}^{n-1}\frac{(-1)^k}n\binom{n-1}k\binom n{n-k}(n-k)(1-x)^kx^{n-k-1}\\ &\qquad=(-1)^{n-1}\sum_{k=0}^{n-1}\binom{n-1}k\binom{n+k-1}k(-x)^k \end{align}

I feel I exhausted all identities/properties of binomials without success. Mathematica says it is true, but how to show it?

First Identity \begin{align} &\sum_{j=n-k}^n\binom{n}{j}(1-x)^{n-j-1}x^{j-1}(j-nx)\\ &=\sum_{j=n-k}^n\binom{n}{j}(1-x)^{n-j-1}x^{j-1}[j(1-x)-(n-j)x]\tag1\\ &=\sum_{j=n-k}^nn\binom{n-1}{j-1}(1-x)^{n-j}x^{j-1}-\sum_{j=n-k}^nn\binom{n-1}{j}(1-x)^{n-j-1}x^{j}\tag2\\ &=\sum_{j=n-k-1}^{n-1}n\binom{n-1}{j}(1-x)^{n-j-1}x^{j}-\sum_{j=n-k}^nn\binom{n-1}{j}(1-x)^{n-j-1}x^{j}\tag3\\[3pt] &=n\binom{n-1}{n-k-1}(1-x)^{k}x^{n-k-1}\tag4\\[9pt] &=(n-k)\binom{n}{n-k}(1-x)^{k}x^{n-k-1}\tag5 \end{align} Explanation:
$$(1)$$: rewrite $$j-nx=j(1-x)-(n-j)x$$
$$(2)$$: $$\binom{n}{j}j=\binom{n-1}{j-1}n$$ and $$\binom{n}{j}(n-j)=\binom{n-1}{j}n$$
$$(3)$$: substitute $$j\mapsto j+1$$ in the left sum
$$(4)$$: combine the cancelling terms
$$(5)$$: $$\binom{n-1}{n-k-1}n=\binom{n}{n-k}(n-k)$$

Second Identity \begin{align} &\sum_{k=0}^{n-1}\frac{(-1)^k}n\binom{n-1}k\binom{n}{n-k}(n-k)(1-x)^kx^{n-k-1}\\ &=\sum_{k=0}^{n-1}(-1)^k\binom{n-1}k\binom{n-1}{n-k-1}(1-x)^kx^{n-k-1}\tag6\\ &=\sum_{k=0}^{n-1}\sum_{j=0}^{n-1}(-1)^k\binom{n-1}{k}\binom{n-1}{n-k-1}\binom{k}{j}(-x)^{k-j}x^{n-k-1}\tag7\\ &=\sum_{k=0}^{n-1}\sum_{j=0}^{n-1}(-1)^j\binom{n-1}j\binom{n-1}{n-k-1}\binom{n-j-1}{k-j}x^{n-j-1}\tag8\\ &=\sum_{j=0}^{n-1}(-1)^j\binom{n-1}{j}\binom{2n-j-2}{n-j-1}x^{n-j-1}\tag9\\ &=(-1)^{n-1}\sum_{k=0}^{n-1}\binom{n-1}{k}\binom{n+k-1}{k}(-x)^k\tag{10} \end{align} Explanation:
$$\phantom{1}(6)$$: $$\binom{n}{n-k}\frac{n-k}n=\binom{n-1}{n-k-1}$$
$$\phantom{1}(7)$$: Binomial Theorem: $$(1-x)^k=\sum_{j=0}^{n-1}\binom{k}{j}(-x)^{k-j}$$
$$\phantom{1}(8)$$: $$\binom{n-1}{k}\binom{k}{j}=\binom{n-1}{j}\binom{n-j-1}{k-j}$$
$$\phantom{1}(9)$$: Vandermonde Identity: $$\sum_{k=0}^{n-1}\binom{n-1}{n-k-1}\binom{n-j-1}{k-j}=\binom{2n-j-2}{n-j-1}$$
$$(10)$$: substitute $$j\mapsto n-k-1$$

For the second one we get

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

The LHS is

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

The coefficient on $$[x^q]$$ where $$0\le q\le n-1$$ of the LHS is

$$\sum_{k=0}^{q} (-1)^{n-k-1} {n-1\choose k} {n-1\choose k} [x^{q-k}] (1-x)^{n-1-k} \\ = \sum_{k=0}^{q} (-1)^{n-k-1} {n-1\choose k} {n-1\choose k} (-1)^{q-k} {n-1-k\choose q-k}.$$

Using the RHS we therefore must show that

$${n-1\choose q} {n+q-1\choose q} = \sum_{k=0}^{q} {n-1\choose k} {n-1\choose k} {n-1-k\choose q-k}.$$

Now note that

$${n-1\choose k} {n-1-k\choose q-k} = \frac{(n-1)!}{k! \times (q-k)! \times (n-1-q)!} = {n-1\choose q} {q\choose k}.$$

This reduces the claim to

$${n+q-1\choose q} = \sum_{k=0}^q {n-1\choose k} {q\choose k}$$

which is

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

Here the coefficient extractor enforces the range and we get

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

as required. This last step can also be done by Vandermonde.

$$\def\peq{\mathrel{\phantom{=}}{}}$$For the first identity, because for $$0 \leqslant j \leqslant n - 1$$,\begin{align*} &\peq \binom{n}{j} j (1 - x)^{n - j} x^{j - 1} - \binom{n}{j + 1} (j + 1) (1 - x)^{n - j - 1} x^j\\ &= \frac{n!}{(j - 1)!\, (n - j)!} (1 - x)^{n - j} x^{j - 1} - \frac{n!}{j!\, (n - j - 1)!} (1 - x)^{n - j - 1} x^j\\ &= \frac{n!}{j!\, (n - j)!} (1 - x)^{n - j - 1} x^{j - 1} (j(1 - x) - (n - j)x)\\ &= \binom{n}{j} (1 - x)^{n - j - 1} x^{j - 1} (j - nx), \end{align*} so\begin{align*} &\peq \sum_{j = n - k}^n \binom{n}{j} (1 - x)^{n - j - 1} x^{j - 1} (j - nx)\\ &= nx^{n - 1} + \sum_{j = n - k}^{n - 1} \left( \binom{n}{j} j (1 - x)^{n - j} x^{j - 1} - \binom{n}{j + 1} (j + 1) (1 - x)^{n - j - 1} x^j \right)\\ &= nx^{n - 1} + \left( \binom{n}{n - k} (n - k) (1 - x)^k x^{n - k - 1} - nx^{n - 1} \right)\\ &= \binom{n}{n - k} (n - k) (1 - x)^k x^{n - k - 1}. \end{align*}

For the second identity, note that$$\begin{gather*} \frac{1}{n} \binom{n - 1}{k} \binom{n}{n - k} (n - k) = \frac{1}{n} · \frac{(n - 1)!}{k!\, (n - k - 1)!} · \frac{n!}{k!\, (n - k)!} · (n - k)\\ = \frac{(n - 1)!}{k!\, (n - k - 1)!} · \frac{(n - 1)!}{k!\, (n - k - 1)!} = \left( \binom{n - 1}{k} \right)^2, \end{gather*}$$ thus dividing by $$x^{n - 1}$$ on both sides of the second identity and denoting $$m = n - 1$$, $$t = -\dfrac{1}{x}$$, it is equivalent to prove that$$\begin{gather*} \sum_{k = 0}^m \left( \binom{m}{k} \right)^2 (t + 1)^k = \sum_{k = 0}^m \binom{m}{k} \binom{m + k}{k} t^{m - k}.\tag{2'} \end{gather*}$$ Consider the polynomial $$(s + t + 1)^m (s + 1)^m$$. Since$$\begin{gather*} (s + t + 1)^m (s + 1)^m = \left( \sum_{k = 0}^m \binom{m}{k} (t + 1)^k s^{m - k} \right) \left( \sum_{k = 0}^m \binom{m}{k} s^k \right),\\ (s + t + 1)^m (s + 1)^m = (s + 1)^m \sum_{k = 0}^m \binom{m}{k} (s + 1)^k t^{m - k} = \sum_{k = 0}^m \binom{m}{k} t^{m - k} (s + 1)^{m + k}, \end{gather*}$$ then$$\begin{gather*} \left( \sum_{k = 0}^m \binom{m}{k} (t + 1)^k s^{m - k} \right) \left( \sum_{k = 0}^m \binom{m}{k} s^k \right) = \sum_{k = 0}^m \binom{m}{k} t^{m - k} (s + 1)^{m + k}.\tag{3} \end{gather*}$$ Treating $$t$$ as a constant and $$s$$ as a variable for the moment, the coefficient of $$s^m$$ of the LHS of (3) is$$\sum_{k = 0}^m \binom{m}{k} (t + 1)^k · \binom{m}{k} = \sum_{k = 0}^m \left( \binom{m}{k} \right)^2 (t + 1)^k,$$ and that of the RHS of (3) is$$\sum_{k = 0}^m \binom{m}{k} t^{m - k} · \binom{m + k}{m} = \sum_{k = 0}^m \binom{m}{k} \binom{m + k}{k} t^{m - k}.$$ Therefore (2$$'$$) is true.

The first Identity follows by induction. When $$k=0$$ $$\begin{eqnarray*} \binom{n}{n} \frac{x^{n-1}}{1-x} (n-nx) = \binom{n}{n} nx^{n-1}. \end{eqnarray*}$$ Now assume the sum for $$k$$ and add the $$(k+1)^{th}$$ term ($$j=n-k-1$$) $$\begin{eqnarray*} \binom{n}{n-k}(n-k)(1-x)^kx^{n-k-1}+\binom{n}{n-k-1}(1-x)^{k}x^{n-k-2}(n-k-1-nx) = \binom{n}{n-k-1}x^{n-k-2}(1-x)^k \left( (k+1)x +(n-k-1)-nx \right) =\binom{n}{n-k-1}(n-k-1)(1-x)^{k+1}x^{n-k-2}. \end{eqnarray*}$$