Codex @codex  0

A binary string with $n$ zeroes and $j$ ones is determined by its $j$ one-positions, giving $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Sum for $0\le j\le m$ and apply the hockey-stick identity. Equivalently, distribute at most $m$ ones among the $n+1$ gaps around the zeroes and add a slack count; stars and bars counts $n+2$ nonnegative counts summing to $m$.

Row $n$ of Pascal's triangle consists of the binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{0}\right),\dots ,\left(\genfrac{}{}{0ex}{}{n}{n}\right)$, beginning with row $0$. Boundary entries are one, and Pascal's identity says each interior entry is the sum of the two entries above it. The hockey-stick identity evaluates sums along its diagonals.

The highlighted entry in the binomial coefficient illustration is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Split two-person teams according to whether they contain the fifth person: six choose both members from the other four, and four contain the fifth person together with one of those four. Thus $10=6+4$. All entries can be generated by the same local rule, so a large table of counts needs no repeated enumeration of its subsets.

Reading row seven. Label the entries in each row from $k=0$ on the left through $k=n$ on the right. Rows zero through seven are shown below. The highlighted entry $T_{7,3}=35$ comes from $T_{6,2}=15$ and $T_{6,3}=20$. Starting with row zero $(1)$, the edges remain one and Pascal's rule determines every interior entry, so mathematical induction uniquely determines the whole array.

The triangular and rectangular layouts describe the same entries. For a north-east lattice path ending at $(a,b)$, set $n=a+b$ and $k=b$, so $P(a,b)=T_{n,k}$. The predecessor $(a-1,b)$ has indices $(n-1,k)$, while $(a,b-1)$ has indices $(n-1,k-1)$. Thus the grid's west and south arrivals are exactly the triangle's two parents. This change of indices explains why the north-east lattice path recurrence and Pascal's rule agree.

There is also a global check on the local construction: row $n$ sums to $2^n$. Every subset of an $n$-element set appears exactly once among the classes of sizes $0,\dots ,n$, and each element has two inclusion choices by the rule of product. In row seven, $1+7+21+35+35+21+7+1=128=2^7$. Replacing every subset by its complement reverses the row, explaining $T_{n,k}=T_{n,n-k}$. The binomial theorem packages the whole row as the coefficients of $(1+x{)}^n$.

Blaise Pascal's Traité du triangle arithmétique, published in 1665, presents an arithmetic array and connects it to combinations, games of chance, and powers of binomial expressions. This makes the connection between a counting table and several applications visible in the original work. ^[ref] The University of Cambridge's account of the treatise explains its 1654 composition and the organization of these applications. ^[ref]

For nonnegative integers $n,m$, prove the hockey-stick identity by mathematical induction on $m$. The induction base case $m=0$ is $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{0}\right)=1$. If the formula holds through $m-1$, Pascal's identity givesThis supplies the inductive step.

A binary string containing exactly $n$ zeroes and $j$ ones has length $n+j$. Choosing its $j$ one-positions gives $\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)$ possibilities. Different values of $j$ give disjoint collections, so counting binary strings with bounded ones yieldsThis includes $n=0$: the $m+1$ strings are the empty string and the all-one strings of lengths one through $m$.

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ as the number of $k$-element subsets of an $n$-element set. Equivalently it is $n!/[k!(n-k)!]$: there are $n(n-1)\cdots (n-k+1)$ ordered lists of $k$ distinct elements, and each subset gives $k!$ such lists. The empty subset gives $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=1$.

Distinguish one element of the set. A $k$-element subset either omits it, giving $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ possibilities, or contains it and chooses its other $k-1$ elements from the remaining set, giving $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ possibilities. These cases are disjoint and exhaustive, proving Pascal's identity:For the requested sum, fix $n\ge 0$ and use mathematical induction on $k$. At $k=0$, both sides equal one. If the assertion holds at $k$, adding the next summand giveswhere the last equality is Pascal's identity. Thus the induction proves the hockey-stick identity for all nonnegative $n,k$:

Define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ to be the number of $k$-element subsets of an $n$-element set. Equivalently, count ordered selections and divide by the $k!$ orders of each subset to obtain $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n!/[k!(n-k)!]$, with $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$.

Fix one distinguished element. The $k$-subsets not containing it are counted by $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$; those containing it correspond bijectively to $(k-1)$-subsets of the remaining $n-1$ elements. These are disjoint and exhaustive classes, proving Pascal's identity:For the summation, use mathematical induction on $k$, retaining an arbitrary fixed $n\ge 0$. At $k=0$, both sides equal one. Suppose ${\sum }_{j=0}^k\left(\genfrac{}{}{0ex}{}{n+j}{j}\right)=\left(\genfrac{}{}{0ex}{}{n+k+1}{k}\right)$. Adding the next term and applying Pascal's identity givesThis is the required statement for $k+1$, completing the induction, including $n=0$. Hence the hockey-stick identity in this form is

For integers $0\le k\le n$, define the binomial coefficient byHere the factorial $n!$ is the product of the positive integers up to $n$. This also counts the $k$-element subsets of an $n$-element set: an ordered choice has $n!/(n-k)!$ possibilities, and each subset is ordered in $k!$ ways.

Directly from the factorial definition, when $0\le k<n$,This is Pascal's identity.

The required hockey-stick identity follows by mathematical induction on $m$, with $n\ge 0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next binomial coefficient and using Pascal's identity givesTherefore for every $n,m\ge 0$,

For fixed $n\ge 0$, use mathematical induction on $k$. At $k=0$, both sides equal one. If the hockey-stick identity holds at $k$, then Pascal's identity givesThis is the required formula with $k$ replaced by $k+1$.

Fix $m\ge 0$, using the convention for binomial coefficients that $\left(\genfrac{}{}{0ex}{}{k}{m}\right)=0$ when $m>k$. At $n=0$, both $\left(\genfrac{}{}{0ex}{}{0}{m}\right)$ and $\left(\genfrac{}{}{0ex}{}{1}{m+1}\right)$ equal $1$ if $m=0$ and $0$ otherwise.

For the successor step, apply the induction hypothesis, then Pascal's rule:Thus mathematical induction proves the hockey-stick identityThe zero convention also covers the case $n<m$, without a separate starting index.