Pascal's Triangle
Pascal's Triangle is a triangular array where each number is the sum of the two numbers above it, generating the binomial coefficients.
Formula
C(n,k) = C(n-1,k-1) + C(n-1,k)
Definition
Pascal's Triangle is a number triangle where each number equals the sum of the two numbers directly above it, and each row gives the coefficients for expanding $(a + b)^n$. The entry in row $n$, position $k$ (0-indexed), is the binomial coefficient $C(n,k) = n!/(k!(n-k)!)$, following the recurrence $C(n,k) = C(n-1,k-1) + C(n-1,k)$; row sums equal $2^n$, diagonal sums give Fibonacci numbers, and rows modulo $2$ produce the Sierpinski fractal. More deeply, it can be interpreted as a discrete convolution table, the Pascal matrix (lower triangular with binomial entries); in characteristic $p$ arithmetic, Kummer's theorem says $p \mid C(m+n, m)$ iff there is a carry in the base-$p$ addition of $m$ and $n$, explaining the fractal structure modulo $p$.
Example
Row $0$: $1$. Row $1$: $1\ 1$. Row $2$: $1\ 2\ 1$. Row $3$: $1\ 3\ 3\ 1$. Row $4$: $1\ 4\ 6\ 4\ 1$. Row $5$, $1\ 5\ 10\ 10\ 5\ 1$, gives the coefficients of $(a+b)^5$, summing to $32 = 2^5$. Lucas' theorem shows $C(n,k)$ is odd iff, in binary, $k$ AND $n = k$, which is exactly why the triangle modulo $2$ produces the Sierpinski triangle at every scale.
Key Insight
Pascal's Triangle contains surprising hidden patterns: powers of $2$ (row sums), Fibonacci numbers (diagonal sums), and the Sierpinski triangle (odd vs. even entries), and the Hockey Stick identity gives elegant closed forms for sums of diagonal runs of combinatorial numbers. Lucas' theorem ($C(m,n) \equiv \prod C(m_i, n_i) \pmod{p}$, using base-$p$ digits) is a cornerstone of combinatorics in finite fields, with applications in coding theory.