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$.
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}$.
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.
-
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?
-
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.
Best Answer
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.