Summation of Alternating Products in Pascal's Triangle: prove $\sum_{k=1}^{n} (-1)^{k+1} x_{k} y_{n-k+1} = 1$

113 Views Asked by At

Dappy is playing around with Pascal's Triangle. While looking for patterns, he finds one equality that he likes a lot:

Pick any spot on Pascal's Triangle that isn't part of the right edge. Call the elements which are to the right of this spot on the same row $x_{k}$, such that $x_{1}$ denotes the position right next to the picked spot, and $x_{n}$ denotes the rightmost element on the row (which would be part of the right edge).

Similarly, denote by $y_{k}$ the elements going in the upwards-right direction.

Help Dappy prove that

$\sum_{k=1}^{n} (-1)^{k+1} x_{k} y_{n-k+1} = 1.$

enter image description here

1

There are 1 best solutions below

2
On BEST ANSWER

Here is one approach.

For some $m\ge 1$, $0\le l\le m-1$, $$ x_k=\binom{m}{k+l}, \ \ y_r=\binom{m-r}{l},\ \ n=m-l $$ so \begin{eqnarray*} &&\sum_{1\le k\le n} (-1)^{k+1} x_{k} y_{n-k+1} \\ &=&\sum_{1\le k\le m-l} (-1)^{k+1} \binom{m}{k+l} \binom{l+k-1}{l}\\ &=&\sum_{1\le k\le m-l} \binom{m}{m-(k+l)} \binom{-l-1}{k-1} \end{eqnarray*} since \begin{eqnarray*} \binom{l+k-1}{l}&=&\binom{l+k-1}{k-1}\\ &=&\frac{(l+k-1)\cdots(l+1)}{(k-1)!}\\ &=&(-1)^{k-1}\frac{(-l-1)\cdots(-l-(k-1))}{(k-1)!}\\ &=&(-1)^{k-1}\binom{-l-1}{k-1}. \end{eqnarray*} So, since $\binom{m}{m-(k+l)}$ is the coefficient of $x^{m-(k+l)}$ in $(1+x)^m$ and $\binom{-l-1}{k-1}$ is the coefficient of $x^{k-1}$ in $(1+x)^{-l-1}$, the sum is the coefficient of $x^{m-l-1}$ in $$ (1+x)^m\cdot (1+x)^{-l-1} = (1+x)^{m-l-1}, $$ which is 1.