Are these two binomial sums known? Proven generalization to the Hockey Stick patterns in Pascal's Triangle

1.7k Views Asked by At

Hockey Stick patterns

English translation. You can see the original - deprecated - in Portuguese here

Hi, I arrived at a generalization for the Hockey Stick Patterns, from our beloved Pascal's Triangle. This generalization involves the product of pairs of binomial numbers, and therefore reassembles Vandermonde's Identity $$\sum \limits_{j=0}^{r}{m\choose j}{q-m\choose r-j}={q\choose r}\tag a$$

According to identity $(8)$ on the wikipedia page Binomial Coefficient we have the following looking similar formula $$\sum \limits_{m=0}^{q}{m\choose j}{q-m\choose r-j}={q+1\choose r+1}\tag b$$

Let's get to the point!


As we know, the RHS Pattern (Right Hockey Stick) is related to columns and tells us that

$${n+1\choose p+1}=\sum \limits_{k=0}^{n-p}{n-k\choose p}\tag 1$$

Letting $d$ be the displacement - referring to columns - between $\displaystyle {n+1\choose p+1}$ and the stick/column itself - what we have today is a particular case when $d=0$ - we'll have the following for $0 \le d \le p-1$:

$${n+1\choose p+1}=\sum \limits_{k=0}^{n-p}{d+k\choose d}{n-d-k\choose p-d}\tag 2$$

In this case, we see a generalization is possible by introducting another column, the column $d$. And both columns are aligned to each other.

Proof

From $(2)$ we have

$k\gt n-p$ $\longrightarrow$ $n-d-k\lt p-d$

$$ \longrightarrow \sum \limits_{k=0}^{n-p}{d+k\choose d}{n-d-k\choose p-d}=\sum \limits_{k=0}^{n}{d+k\choose d}{n-d-k\choose p-d}$$

Letting

$m = d + k; j = d; q = n; r = p$;

And

$0\leq k\leq n$ $\longrightarrow$ $d\leq d+k\leq n+d$ $\longrightarrow$ $j\leq m\leq q+j$

So, we have

$$\sum \limits_{k=0}^{n}{d+k\choose d}{n-d-k\choose p-d}=\sum \limits_{m=j}^{q+j}{m\choose j}{q-m\choose r-j}$$

$m<j$ $\longrightarrow$ $\displaystyle{m\choose j}=0$

$m>q$ $\longrightarrow$ $\displaystyle{q-m\choose r-j}=0$

$$ \longrightarrow \sum \limits_{m=j}^{q+j}{m\choose j}{q-m\choose r-j}=\sum \limits_{m=0}^{q}{m\choose j}{q-m\choose r-j}$$

According to $(b)$,

$$\sum \limits_{m=0}^{q}{m\choose j}{q-m\choose r-j}={q+1\choose r+1}={n+1\choose p+1}$$

As expected.


Now let's get to the LHS pattern (Left Hockey Stick) - which is related to diagonals - that says

$${n+1\choose p}=\sum \limits_{k=0}^p{n-k\choose p-k}\tag 3$$

Calling $d$ the displacement - referring to diagonals - between $\displaystyle {n+1\choose p}$ and the stick/diagonal - what we have today is a particular case when $d=0$. For $0 \le d \le n-p-1$, we have

$${n+1\choose p}=\sum \limits_{k=0}^p {d+k\choose k}{n-d-k\choose p-k}\tag 4$$

Now, we see a generalization is possible by introducting another diagonal, the diagonal $d$. And both diagonals are aligned to each other.

Proof

From $(4)$ we have $$\sum \limits_{k=0}^p {d+k\choose k}{n-d-k\choose p-k}=\sum \limits_{k=0}^p {d+k\choose d}{n-d-k\choose n-p-d}$$

$k\gt p$ $\longrightarrow$ $n-d-k\lt n-p-d$

$$ \longrightarrow \sum \limits_{k=0}^{p}{d+k\choose d}{n-d-k\choose n-p-d}=\sum \limits_{k=0}^{n}{d+k\choose d}{n-d-k\choose n-p-d}$$

Letting

$m = d + k; j = d; q = n; r = n-p$;

And

$0\leq k\leq n$ $\longrightarrow$ $d\leq d+k\leq n+d$ $\longrightarrow$ $j\leq m\leq q+j$

So, we have

$$\sum \limits_{k=0}^{n}{d+k\choose d}{n-d-k\choose n-p-d}=\sum \limits_{m=j}^{q+j}{m\choose j}{q-m\choose r-j}$$

$m<j$ $\longrightarrow$ $\displaystyle{m\choose j}=0$

$m>q$ $\longrightarrow$ $\displaystyle{q-m\choose r-j}=0$

$$ \longrightarrow \sum \limits_{m=j}^{q+j}{m\choose j}{q-m\choose r-j}=\sum \limits_{m=0}^{q}{m\choose j}{q-m\choose r-j}$$

According to $(b)$,

$$\sum \limits_{m=0}^{q}{m\choose j}{q-m\choose r-j}={q+1\choose r+1}={n+1\choose n-p+1}={n+1\choose p}$$

As expected.


Question. Are $(2)$ and $(4)$ already known?

1

There are 1 best solutions below

1
On BEST ANSWER

To repeat my comment: (2) is equivalent to identity (8) on the wikipedia page Binomial coefficient.