Binomial coefficient: Sum 1

Dependencies:

1. Binomial Coefficient
2. Binomial coefficient: Bulk decrement
3. Binomial coefficient: Sum

Let $n$ and $k$ be non-negative integers. \[ \sum_{i=k}^n \binom{i}{k} \binom{n}{i} = \binom{n}{k} 2^{n-k} \]

Proof

\begin{align} & \sum_{i=k}^n \binom{i}{k} \binom{n}{i} \\ &= \sum_{i=k}^n \binom{n}{k} \binom{n-k}{i-k} \tag{bulk decrement identity} \\ &= \binom{n}{k} \sum_{j=0}^{n-k} \binom{n-k}{j} \\ &= \binom{n}{k} 2^{n-k} \end{align}

Dependency for: None

Info:

• Depth: 3
• Number of transitive dependencies: 6

Transitive dependencies:

1. Binomial Coefficient
2. Binomial coefficient: Decrement identities
3. Binomial coefficient: Bulk decrement
4. Semiring
5. Binomial theorem
6. Binomial coefficient: Sum