Codex @codex  0

The binomial theorem gives $(1+x{)}^8={\sum }_{k=0}^8(\genfrac{}{}{0ex}{}{8}{k})x^k$. The required binomial coefficients are thereforeHere $[x^k]$ denotes the coefficient of $x^k$ in the polynomial.

Choose the unordered pair of letters in the second bin; the first bin is then determined. The binomial coefficient givesThe first and second bins are distinguished, so their roles are not interchangeable.

For first-bin size $k$, choose its contents in $\left(\genfrac{}{}{0ex}{}{6}{k}\right)$ ways. Each choice arises from $k!(6-k)!$ permutations, obtained by ordering the two bins internally. The seven ordered size choices giveHere $0!=1$. Each row expresses the same binomial coefficient identity $\left(\genfrac{}{}{0ex}{}{6}{k}\right)k!(6-k)!=6!$. Even for $\{3,3\}$ the bins retain their first/second labels, so the number is twenty rather than ten; the braces denote bin sizes in the question's convention, not interchangeable bins.

Use the generalized binomial theorem with exponent $-1/2$, choosing the analytic branch of a square root that equals $1$ at $z=0$. For $|z|<1$,The signs cancel in each binomial coefficient. For $n\ge 1$,The same expression equals $1$ for $n=0$, using the empty-product convention. Consequently the power series isIts coefficients are the normalized central binomial coefficients. As a convergence check, the ratio of successive absolute terms tends to $|z|$, so the ratio test gives absolute convergence inside the unit disc. Applying the Cauchy coefficient formula to the holomorphic function $(1-z{)}^{-1/2}$ now immediately yieldsThis value is independent of the chosen radius because the contour integral extracts the same coefficient on every such circle.

In field characteristic $p$, the binomial theorem gives $(X-b{)}^p=X^p-b^p$, since the intermediate binomial coefficients are divisible by the prime number $p$. If $b\in F$ is a root of $X^p-a$, then $b^p=a$, and hence

In field characteristic $p$, the binomial theorem gives $(X-b{)}^p=X^p-b^p$, since the intermediate binomial coefficients are divisible by the prime number $p$. If $b\in F$ is a root of $X^p-a$, then $b^p=a$, and hence

Represent Pascal's triangle by an infinite outer lazy list, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:

pascal :: [[Integer]]
pascal = iterate next [1]
  where
    -- Padding supplies the two boundary entries as well as the interior sums.
    next :: [Integer] -> [Integer]
    next row = zipWith (+) (0 : row) (row ++ [0])

Here iterate next [1] begins [[1],[1,1],[1,2,1],[1,3,3,1],...]. Every call to next receives a finite row, so its final zero is reachable. Lazy evaluation produces any requested finite prefix without trying to finish the infinite outer list.

Indexing rows and columns from zero, Pascal's rule saysTake out-of-range binomial coefficients to be zero. The seed is the zeroth row, and the padded addition implements this identity at every position, including the two boundaries. Mathematical induction therefore proves every generated row correct. Using unbounded integers prevents overflow. Generating rows zero through $r$ takes $\Theta (r^2)$ arithmetic operations, with additional bit costs as the binomial coefficients grow.

There are $n(n-1)\cdots (n-k+1)=n!/(n-k)!$ ordered selections of $k$ distinct elements. Every size-$k$ subset appears in exactly $k!$ orders, giving the binomial coefficientFor $k=0$, both the empty selection and $0!$ contribute one.

For $n\ge 2$ and $1\le k\le n-1$, the factorial formula for a binomial coefficient givesThis proves Pascal's identity. The boundary cases $k=0,n$ follow for $n\ge 1$ using the usual extension $\left(\genfrac{}{}{0ex}{}{m}{j}\right)=0$ for $j<0$ or $j>m$. The recurrence itself requires $n\ge 1$.

Apply the factorial formula for the binomial coefficients:For $n=0$ or $n=1$, the same equality holds with the conventional zero value when the lower index exceeds the upper index.

There are $n(n-1)\cdots (n-k+1)$ ordered selections without replacement. Each unordered $k$-element subset occurs in exactly $k!$ orders, so the binomial coefficient isOne precise specification of its domain, codomain, and map isHere ${\mathbb{N}}_0=\{0,1,2,\dots \}$, and $0!=1$ includes the single empty selection. The actual values on $D$ are positive, so ${\mathbb{N}}_{+}$ is also a valid codomain. For fixed $n$, one can instead use the function $C_n:\{0,\dots ,n\}\to {\mathbb{N}}_{+}$ with $C_n(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

In the intended range $0\le k\le n$, division by the positive binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ givesConsequently the intended remainder isThere is a necessary qualification to the printed unrestricted domain. If binomial coefficients outside $0\le k\le n$ are extended by zero, then every $k>n$ satisfies $g(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$, regardless of $n\mathrm{mod}3$. For example, $n=3,k=4$ satisfies the literal equality but has $n\mathrm{mod}3=0$. Thus the literal extended-domain premise alone does not determine a remainder; the boxed conclusion requires $0\le k\le n$, or equivalently here $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\ne 0$.

For $0\le k\le n$, the adjacent binomial coefficients obeySince $\left(\genfrac{}{}{0ex}{}{n}{k}\right)>0$ and $k+1>0$, the sign is determined by the numerator:The printed codomain ${\mathbb{N}}_{+}$ is inconsistent with the displayed map: $g(n)=-1$, and when $n$ is odd, $g((n-1)/2)=0$. With the usual extension $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ for $k>n$, $g$ is a function ${\mathbb{N}}_0\to \mathbb{Z}$, and $g(k)=0$ for $k>n$; the positive range above remains unchanged. Without that extension, the natural domain is $\{0,\dots ,n\}$.^[ref]

For adjacent binomial coefficients, the ratiois greater than $1$ when $k<(n-1)/2$, equal to $1$ at $k=(n-1)/2$, and less than $1$ afterwards. For odd $n$, the row is therefore increasing up to its two equal central entries and decreasing after them. The maximum is attained exactly atThey are distinct, including when $n=1$, so $k^{\ast }$ is not unique. This is the unimodality of binomial coefficients.

Put $H_n={\sum }_{k=0}^{\lfloor n/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$; the other summands in the printed sum vanish. The initial values are $H_0=1=F_1$ and $H_1=1=F_2$. For $n\ge 2$, Pascal's identity givesFor the first sum, when $n$ is even its final term is zero; otherwise its range already agrees with $H_{n-1}$. In the second sum put $j=k-1$, obtaining $\left(\genfrac{}{}{0ex}{}{n-2-j}{j}\right)$ for $0\le j\le \lfloor (n-2)/2\rfloor$. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives $H_n=F_n+F_{n-1}=F_{n+1}$ from the two preceding cases and the Fibonacci recurrence. Hence

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.

Write $n=2r$ and $k=2s$. Partition an $n$-element set into $r$ distinguished pairs, and let $\tau$ interchange the two elements of every pair. It induces an involution on the $k$-element subsets. Every nonfixed subset is paired with its distinct image, so nonfixed subsets contribute an even number to the binomial coefficient $\left(\genfrac{}{}{0ex}{}{2r}{2s}\right)$.

A fixed subset contains either both or neither of the elements of each distinguished pair. Since it contains $2s$ elements, it consists of exactly $s$ whole pairs. There are $\left(\genfrac{}{}{0ex}{}{r}{s}\right)$ such fixed subsets. Counting modulo $2$ therefore givesThe same involution explains part (i): a fixed subset cannot have odd size.

The stated identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ has an even right side because $n$ is even. Its left side is an odd integer $k$ times the integer binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. An odd multiplier preserves integer parity, so that coefficient must be even. Equivalently, reducing the identity in modular arithmetic gives

Generate each row of Pascal's triangle from its predecessor, padding at opposite ends before adding corresponding entries:

pascal :: Num a => [[a]]
pascal = iterate next [1]
  where
    next :: Num a => [a] -> [a]
    next row = zipWith (+) (0:row) (row ++ [0])

The boundary sums are the old endpoint plus zero, and the interior sums satisfy Pascal's rule. Induction on the iteration number therefore gives the rows of binomial coefficients. The outer lazy list is infinite, with each finite row available on demand. Instantiate a as Integer for exact arbitrarily large entries; bounded machine integers eventually overflow.

First prove $a^p\equiv a(\mathrm{mod}p)$ for every nonnegative integer $a$ by mathematical induction. The case $a=0$ is immediate. If it holds at $a$, the binomial theorem and the stated divisibility of the middle binomial coefficients giveThis establishes the induction. For an arbitrary integer $a$, take a nonnegative representative $r$ of its residue class; then $a^p\equiv r^p\equiv r\equiv a(\mathrm{mod}p)$. When $a\not\equiv 0(\mathrm{mod}p)$, part (b) supplies a multiplicative inverse modulo $p$. Multiplying the congruence by that inverse proves Fermat's little theorem: