5
$\begingroup$

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?

$\endgroup$
3
+200
$\begingroup$

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$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.