Introduction

Fluency with binomial coefficients is a great help in combinatorial arguments about graphs. You should learn to juggle with binomial coefficients as easily as you juggle with normal algebraic equations.

Techniques

• Substitute specific values in the general equations, e.g. careful choice of x and y in:

${\displaystyle (x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}.}$

• Sledgehammer proof using recursion formula. You may find it helpful to 'chase' binomial coefficients on a diagram of Pascal's triangle.
• Differentiation of a previous identity to get a new one.
• Combinatorial arguments about permutations and combinations.

Worked Examples

The Identities

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$

${\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}$

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

${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$

${\displaystyle \displaystyle \sum _{k=0}^{n}{\tbinom {n}{k}}^{2}={\tbinom {2n}{n}}.}$

${\displaystyle \displaystyle \sum _{k=0}^{n}{\tbinom {n}{k}}{\tbinom {n}{n-k}}={\tbinom {2n}{n}}.}$

${\displaystyle \sum _{k=0}^{n}k{\tbinom {n}{k}}=n2^{n-1}}$

${\displaystyle \sum _{k=0}^{n}k^{2}{\tbinom {n}{k}}=(n+n^{2})2^{n-2}}$

${\displaystyle \sum _{m=0}^{n}{\tbinom {m}{j}}{\tbinom {n-m}{k-j}}={\tbinom {n+1}{k+1}}}$

${\displaystyle \sum _{m=0}^{n}{\tbinom {m}{k}}={\tbinom {n+1}{k+1}}\,.}$

${\displaystyle \sum _{k=0}^{\lfloor {\frac {n}{2}}\rfloor }{\tbinom {n-k}{k}}=F(n+1)}$

where F(n) denote the n^th Fibonacci number.

${\displaystyle \sum _{j=k}^{n}{\tbinom {j}{k}}={\tbinom {n+1}{k+1}}}$

${\displaystyle \sum _{j=0}^{k}(-1)^{j}{\tbinom {n}{j}}=(-1)^{k}{\tbinom {n-1}{k}}}$

${\displaystyle \sum _{j=0}^{n}(-1)^{j}{\tbinom {n}{j}}=0}$

${\displaystyle \sum _{i=0}^{n}{i{\binom {n}{i}}^{2}}={\frac {n}{2}}{\binom {2n}{n}}}$

${\displaystyle \sum _{i=0}^{n}{i^{2}{\binom {n}{i}}^{2}}=n^{2}{\binom {2n-2}{n-1}}}$.

${\displaystyle \sum _{k=q}^{n}{\tbinom {n}{k}}{\tbinom {k}{q}}=2^{n-q}{\tbinom {n}{q}}}$

Applications

• Find probability of cycles of certain length in a permutation.