Binomial coefficient: Bulk decrement

Dependencies:

1. Binomial Coefficient
2. Binomial coefficient: Decrement identities

\[ \binom{n}{i} = \frac{\binom{n}{k}}{\binom{i}{k}} \binom{n-k}{i-k} \]

Proof

Repeatedly apply the decrement identity to get

\[ \binom{n}{i} = \frac{n(n-1)\ldots(n-k+1)}{i(i-1)\ldots(i-k+1)} \binom{n-k}{i-k} \]

\begin{align} n(n-1)\ldots(n-k+1) &= k!\binom{n}{k} & i(i-1)\ldots(i-k+1) &= k!\binom{i}{k} \end{align}

Dependency for:

1. Binomial coefficient: Sum 1

Info:

• Depth: 2
• Number of transitive dependencies: 2

Transitive dependencies:

1. Binomial Coefficient
2. Binomial coefficient: Decrement identities