Combinatorial identities

Here’s some random combinatorial identities.

Theorem 1 For any {n\geqslant 1} and {1\leqslant k\leqslant n-1},

\displaystyle \binom nk = \binom{n-1}k + \binom{n-1}{k-1}.

Proof: For a computational proof,

\displaystyle  \begin{aligned} \binom{n-1}k + \binom{n-1}{k-1} &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-1-(k-1))!}\\ &= \frac{(n-1)!}{k!(n-1-k)!} + \frac{(n-1)!}{(k-1)!(n-k)!}\\ &= \frac{(n-1)!(n-k)}{k!(n-k)!} + \frac{(n-1)!k}{k!(n-k)!}\\ &= \frac{(n-1)!(n-k+k)}{k!(n-k)!}\\ &= \frac{n!}{k!(n-k)!}\\ &= \binom nk. \end{aligned}

For a combinatorial proof, the LHS is the number of {k}-element subsets of {[n]} and the RHS is the number of {k}-element subsets of {[n-1]} plus the number of {k-1}-element subsets of {[n-1]}. Since each {k}-element subset of {[n]} either has {k} elements or {k-1} elements of {[n-1]}, the two quantities are equal. \Box

Theorem 2 For any {n\geqslant 0},

\displaystyle \sum_{k=0}^n \binom nk = 2^n.

Proof: For a computational proof, note that

\displaystyle \sum_{k=0}^0 \binom 0k = 1 = 2^0,

and if the statement holds for some {n\geqslant0} then

\displaystyle  \begin{aligned} \sum_{k=0}^{n+1}\binom {n+1}k &= \sum_{k=0}^{n+1}\left[\binom nk + \binom n{k-1}\right]\\ &= \sum_{k=0}^n \binom nk + \sum_{k=1}^{n+1}\binom n{k-1}\\ &= 2\sum_{k=0}^n \binom nk\\ &= 2\cdot 2^n = 2^{n+1}. \end{aligned}

For a combinatorial proof, the LHS is the sum of the number of {k}-element subsets of {[n]} for {k=0,1,\ldots, n} and the RHS is the number of subsets of {[n]}. Since each subset of {[n]} has exactly one of {0,1,\ldots,n} elements, the two quantities are equal. \Box

Theorem 3 For any {n\geqslant 0},

\displaystyle \sum_{k=0}^n k\binom nk = n2^{n-1}.

Proof: We compute:

\displaystyle  \begin{aligned} \sum_{k=0}^n k\binom nk &= \sum_{k=1}^n k\frac{n!}{k!(n-k)!}\\ &= n\sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!}\\ &= n\sum_{k=0}^{n-1}\frac{(n-1)!}{k!(n-(k+1))!}\\ &= n\sum_{k=0}^{n-1}\binom {n-1}k\\ &= n2^{n-1}. \end{aligned}

\Box

Theorem 4 For any {n\geqslant1} and {1\leqslant k\leqslant n},

\displaystyle \binom nk = \frac nk\binom{n-1}{k-1}.

Proof: Since

\displaystyle \binom{n-1}k = \frac{(n-1)!}{k!(n-1-k)!} = \frac{(n-1)!(n-k)}{k(k-1)!(n-k)!},

we have

\displaystyle  \begin{aligned} \binom nk &= \binom{n-1}{k-1} + \binom{n-1}k\\ &= \binom{n-1}{k-1} + \frac{n-k}k\binom{n-1}{k-1}\\&=\frac nk\binom{n-1}{k-1}. \end{aligned}

\Box

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s