Is this a new discovery in the diagonals of Pascal's triangle?

Question

To preface, I am a senior in high school and my knowledge of combinatorics and its notation is quite limited. I came across Pascal's triangle while drilling the binomial expansions into my head, and I quickly became fascinated with its various properties. When I looked at the diagonals, I wanted to challenge myself by coming up with formulae for the diagonals, and I began with the first two diagonals.

Once again, I am not familiar with the standard notation, so please look past it for now. However, I would greatly appreciate advice on what I should change, and where I can learn the standard notation. I am making this post off of a "paper" I wrote to collect my thoughts, screenshots of said paper will be used.

For the diagonals, I will use $D_n$, where each value of $n$ represents each diagonal. (ex: $D_2 = [1, 2, 3, 4, 5, 6\cdots]$

For the numbers within the sets of $D_n$, I will use $d_n$.
$D_n = [d_1, d_2, d_3\cdots]$

So for the first two diagonals

$D_1: d_n=1$

$D_2: d_n=x$

As I approached the third diagonal, my mind immediately jumped to recursion, and the formula for $D_n$ would be

$D_3: d_n= d_{n-1} + x$; $d_{n<1} = 0$ (this applies for all subsequent formulae)

The formula for $D_4$ took me a little longer, but I knew the set for $D_4$ was larger than $D_3$, so its formula should contain the formula from $D_3$ and another positive term. After some messing around, I arrived at making the next term as follows.

$D_4: d_n= d_{n-1} + x + (d_{n-1} - d_{n-2})$

The next day, I continued my brainstorming and made the next 2 formulae.

$D_5: d_n= d_{n-1} + x + 2(d_{n-1} - d_{n-2}) - (d_{n-2} - d_{n-3})$

$D_6: d_n= d_{n-1} + x + 3(d_{n-1} - d_{n-2}) - 3(d_{n-2} - d_{n-3})+(d_{n-3} - d_{n-4})$

I hit a brick wall for a little while, and I stared at the formulae I had for hours until I noticed something. I looked at the coefficients of the terms, and saw a pattern forming; the coefficients follow Pascal's triangle. This can be visualized best in the image below, which includes the formulae from $D_3$ through $D_8$.

Apologies for my handwriting

The coefficients of the formulae appear to follow the values of Pascal's triangle indefinitely. It is worth noting for sets $D_n$ where $d_2$ is an odd number, the coefficients are always central binomial rows and the last term is always negative. And for sets $D_n$ where $d_2$ is an even number, the coefficients are always central trinomial rows and the last term is always positive. With this in mind, I followed the pattern to make the formula for $D_{11}$, and then used it to solve $d_{10}$ of $D_{11}$.

again, handwriting

So this is where I am at right now, nothing much else besides that except my final questions and some basic proof at the very bottom.

1. Have I found something new? Not the formula's use itself, because I know there are other much more efficient methods, but the pattern that I am seeing in the coefficients. Do other methods for getting a number in a diagonal of Pascal's triangle show the rows of Pascal's triangle like this method is?

2. Regardless of if this is new or not, can I get some help with the notation? I know there is some way to make and notate a formula for formulae.

$D_3$ $D_4$ $D_5$

$D_6$ $D_7$ $D_8$

Answer 1

Well spotted!

This is due to important known properties of the binomial coefficients.

What you write as entry $d_n$ in the diagonal $D_k$ is usually written as the binomial coefficient $\binom {n-1+k-1}{k-1}$. To avoid subtracting $1$ all the time, I’ll write the pattern you found for entry $d_{n+1}$ in the diagonal $D_{k+1}$. This is

$$ \binom {n+k}k=\binom{n+k-1}k+n+1+\sum_{j=1}^{k-2}(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right] $$

(where I’ve assumed that, as discussed in the comments, you meant $x$ to represent $n$ – usually we stick with one name for a variable).

To simplify this, note that the two terms on either side of the equals sign are precisely what you get if you extend the sum down to $j=0$, so you can write this as

$$ 0=n+1+\sum_{j=0}^{k-2}(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]\;. $$

You can replace the upper limit of the sum by $n$, because any terms with $j\gt k-2$ don’t contribute since the first factor is zero and any terms with $j\gt n$ don’t contribute since the second factor is zero (there are zero ways to choose $k$ from $n$ objects when $k\gt n$); thus, equivalently,

$$ 0=n+1+\sum_{j=0}^n(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]\;. $$

Next, you can apply the basic recurrence relation for Pascal’s triangle,

$$ \binom nk=\binom{n-1}k+\binom{n-1}{k-1}\;, $$

to replace the difference in brackets by a single binomial coefficient:

$$ 0=n+1+\sum_{j=0}^n(-1)^{j+1}\binom{k-2}j\binom{n+k-j-1}{k-1}\;, $$

or

$$ \sum_{j=0}^n(-1)^j\binom{k-2}j\binom{n+k-j-1}{k-1}=n+1\;. $$

This is the main content of your formula, stripped of unnecessary complications. I wouldn’t call this a known equation in this exact form, but it’s a type of relationship among binomial coefficients that’s well known and often useful. You can derive it by applying the following transformations. First, use the symmetry of the binomial coefficients,

$$ \binom nk=\binom n{n-k}\;, $$

which leads to

$$ \sum_{j=0}^n(-1)^j\binom{k-2}j\binom{n+k-j-1}{n-j}=n+1\;. $$

Now apply the formula for negating the upper coefficient, which is

$$ \binom nk=(-1)^k\binom{k-n-1}k\;, $$

to the second factor. (Here I’m using a generalization of the binomial coefficients to negative integers; these coefficients don’t appear in Pascal’s triangle, but they can be very useful.) This leads to

$$ (-1)^n\sum_{j=0}^n\binom{k-2}j\binom{-k}{n-j}=n+1\;. $$

Now comes a nice relationship known as Vandermonde’s identity:

$$ \binom{m+n} r=\sum_{k=0}^r\binom mk\binom n{r-k}\;. $$

If $m$, $n$ and $r$ are non-negative integers, this expresses the fact that choosing $r$ from $m+n$ objects can be done by choosing $k$ from $m$ of the objects and $r-k$ from the other $n$ objects. When (as in our case) $m$ and $n$ are not restricted to non-negative integers, the identity is also known as the Chu–Vandermonde identity. Applying it with $m=k-2$ and $n=-k$, and thus $m+n=-2$, leads to

$$ (-1)^n\binom{-2}n=n+1\;. $$

And that’s just the definition of $\binom{-2}n$:

$$ \binom{-2}n=(-1)^n\binom{n-(-2)-1}n=(-1)^n\binom{n+1}n=(-1)^n\binom{n+1}1=(-1)^n(n+1)\;. $$

Of course I applied the steps in the wrong direction, starting from your observation, but they’re all equivalences, so you can go in the other direction to derive your formula.

So, well done! You found quite a non-trivial relationship among the binomial coefficients that takes a number of important results to derive. Note that you can derive lots of similar relationships by using other negative integers instead of $-2$.

This may all be a bit much to take in – feel free to ask further questions, and let me know in the comments if you do.

Answer 2

It is more convenient to start indexing diagonals starting with $k=0$ and also index the elements on those diagonal starting with $n=0$. Then the $n$th element on the $k$th diagonal of the Pascal triangle is $\binom{n+k}{k}$. You are looking at the properties of the sequence of the differences of their consecutive terms, i.e. $$ \binom{n+k}{k}-\binom{n-1+k}{k}. $$ You would like to show that $$ \sum_{j=0}^{k-2}{(-1)^j\binom{k-2}{j}\left(\binom{n+k-j}{k}-\binom{n+k-j-1}{k}\right)}=n+1. $$ Let us collect terms differently. In this rewritten sum, consider the coefficient at $\binom{n+k-j}{k}$. It appears in two terms, once with a plus sign and once with a minus sign (except for the terms $\binom{n+k}{k}$ and $\binom{n}{k}$, which you can check have coefficients $1$ for $j=0$ and $(-1)^k$ for $j=k$). Therefore, the coefficient at $\binom{n+k-j}{k}=\binom{n+k-(j-1)-1}{k}$ is $$ (-1)^j\binom{k-2}{j}-(-1)^{j-1}\binom{k-2}{j-1}=(-1)^j\left(\binom{k-2}{j}+\binom{k-2}{j-1}\right)=(-1)^j\binom{k-1}{j}. $$ As you can see, this formula holds for $j=0$ and $j=k$ as well. Thus, we really want to prove that $$ \sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}\binom{n+k-j}{k}}=n+1. $$ A nice trick to use here (e.g., to avoid generating functions) is that $$ \binom{n+k-j}{k}=\binom{k+n-j}{n-j}=\frac{(k+n-j)(k+n-j-1)\cdots(k+1)}{(n-j)!}=(-1)^{n-j}\frac{(-k-1)\cdots(-k-(n-j-1))(-k-(n-j))}{(n-j)!}=\binom{-k-1}{n-j}. $$ If you have not seen negative numbers in the binomial coefficients before, this trick may seem strange, but consider that if we write $\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}$, the value $n$ appears only in the numerator and only in finitely many factors, so it can be any real number! (And even more, but we don't need that now.)

Thus, we have $$ \begin{split} \sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}\binom{n+k-j}{k}}&=\sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}(-1)^{n-j}\binom{-k-1}{n-j}}\\ &=(-1)^n\sum_{j=0}^{k-1}{\binom{k-1}{j}\binom{-k-1}{n-j}}. \end{split} $$ Notice that the bottom indices always add up to $n$, and the top indices are constant. Thus, by the Vandermonde identity, $$ (-1)^n\sum_{j=0}^{k-1}{\binom{k-1}{j}\binom{-k-1}{n-j}}=(-1)^n\binom{k-1+(-k-1)}{n}=(-1)^n\binom{-2}{n}. $$ But, just like before, $$ \binom{-2}{n}=\binom{-1-1}{n}=(-1)^n\binom{n+1}{n}=(-1)^n(n+1), $$ so $$ (-1)^n\binom{-2}{n}=(-1)^n(-1)^n(n+1)=(-1)^{2n}(n+1)=n+1, $$ as desired.

Answer 3

As joriki and Alexander both derived, the pattern you noticed is equivalent to $$ \sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}\binom{n+k-j}{k}} $$ We can give a combinatorial proof of this identity, using the principle of inclusion exclusion.

Let $S$ be the set of all lattice paths from $(0,0)$ to $(n,k)$, consisting of $n+k$ steps, where each step is either one unit up or one unit to the right, so $|S|=\binom{n+k}{k}$. Then, for each $i\in \{1,\dots,k-1\}$, let $E_i$ be the set of paths in $S$ which include at least one edge of the form $$ (x,i)\to (x+1,i), $$ for some $x\in \{0,1,\dots,n\}$. That is, there is at least one horizontal step at a height of $i$. We use the principle of inclusion-exclusion to count the complement of $(E_1\cup \dots \cup E_{k-1})$: $$ \begin{align} |S\setminus (E_1\cup \dots\cup E_{k-1})| &=\sum_{j=0}^{k-1}(-1)^j\sum_{1\le i_1<\dots<i_j\le k-1}|E_{i_1}\cap \dots \cap E_{i_{j}}| \\&= \sum_{j=0}^{k-1}(-1)^j\binom{k-1}j|E_{1}\cap \dots \cap E_{j}| \\&= \sum_{j=0}^{k-1}(-1)^j\binom{k-1}j\binom{n+k-j}{k}. \end{align} $$ To see why $|E_{1}\cap \dots \cap E_{j}|=\binom{n+k-j}{k}$, imagine taking a path in $S$ which has at least one horizontal step at levels $1$ through $j$, and deleting the first horizontal step at each level $1$ through $j$. The path will contract horizontally, so what remains is a path from $(0,0)$ to $(n-j,k)$. The procedure is reversible, so $|E_{1}\cap \dots \cap E_{j}|$ is in bijection with the set of all paths in a $(n- j)\times k$ rectangle, which are enumerated by $\binom{n+k-j}k$.

All that remains is to prove that $|S\setminus (E_1\cup \dots\cup E_{k-1})|=n+1$. Indeed, a path without horizontal steps at levels $1$ through $k-1$ must consist of $x$ horizontal steps at level zero, followed by $k$ vertical steps to the top of the grid, and completed by $n-x$ horizontal steps. Since $x\in \{0,1,\dots,n\}$, there are $n+1$ ways to choose such a path.

---

More generally, the same proof shows

$$ \sum_{j=0}^k(-1)^k \binom{k}j \binom{n+m-j}{m}=\binom{n+m-k}{n} $$

Answer 4

By way of enrichment, to prove

$$\sum_{j=0}^k (-1)^j {k\choose j} {n+m-j\choose m} = {n+m-k\choose n}$$

we can use a coefficient extractor to get on the LHS that it is

$$[z^m] (1+z)^{n+m} \sum_{j=0}^k (-1)^j {k \choose j} (1+z)^{-j} = [z^m] (1+z)^{n+m} \left[1-\frac{1}{1+z}\right]^k \\ = [z^m] (1+z)^{n+m-k} z^k = [z^{m-k}] (1+z)^{n+m-k} = {n+m-k\choose m-k} = {n+m-k\choose n}$$

as claimed.