Proving two binomial identities

Question

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?

Answer 1

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$

Answer 2

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.

Answer 3

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*}

Answer 4

$\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.