📂Lemmas

Derivation of Pascal's Identity

Formula ¹

The following binomial identity holds. $$ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} $$

Derivation

$$ \begin{align*} & \binom{n}{k} + \binom{n}{k+1} \\ =& {\frac{ n! }{ k! (n-k)! }} + {\frac{ n! }{ (k+1)! (n-k-1)! }} \\ =& {\frac{ n! (k+1) }{ (k+1)! (n-k)! }} + {\frac{ n! (n-k) }{ (k+1)! (n-k)! }} \\ =& {\frac{ n! (k+1) + n! (n-k) }{ (k+1)! (n-k)! }} \\ =& {\frac{ n! (n+1) }{ (k+1)! (n-k)! }} \\ =& \binom{n+1}{k+1} \end{align*} $$

■