Binomial coefficient: Sum 2

Dependencies:

1. Binomial Coefficient
2. Binomial coefficient: Additive recursion

\[ \sum_{i=k}^n \binom{i}{k} = \binom{n+1}{k+1} \]

Proof

\begin{align} & \sum_{i=k}^n \binom{i}{k} \\ &= \sum_{i=k} \left( \binom{i+1}{k+1} - \binom{i}{k+1} \right) \tag{additive recursion formula} \\ &= \binom{n+1}{k+1} - \binom{k}{k+1} \tag{telescoping series} \\ &= \binom{n+1}{k+1} \end{align}

Dependency for:

1. Number of tuples with bounded sum
2. Number of tuples with fixed sum
3. Binomial coefficient: Sum 4

Info:

• Depth: 2
• Number of transitive dependencies: 2

Transitive dependencies:

1. Binomial Coefficient
2. Binomial coefficient: Additive recursion