Binomial Coefficients and Identities (KR 6.4)

Binomial Theorem

let $x$ and $y$ be variables, let $n$ be a nonnegative integer, then:

$(x+y)^n = \sum_{j=0}^n\binom{n}{j}x^{n-j}y^j = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y+…+\binom{n}{n-1}xy^{n-1}+\binom{n}{n}y^n$

• essentially, when expanding $(x+y)^n$, the coefficients are directly related to combinations
• this can be visualized with Pascal’s Triangle

Pascal’s Identity

If $n$ and $k$ are integers with $n \geq k \geq 0$, then:

$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$

Combinatorial interpretation

• the number of ways to choose $k$ things from $n+1$ things, let $A$ be a thing.
• this is equal to the total number of ways to:
  • choose $k-1$ things from $n$ things (excluding $A$) and include $A$ plus
  • the number of ways to choose $k$ things from $n$ things (excluding $A$)
• pascal’s triangle combination visual
• pascal’s triangle properties

Useful Identities

For $n \geq 0$, $\sum_{k=0}^n\binom{n}{k} = 2^n$

For $n \geq 1$, $\sum_{i=0}^n(-1)^i\binom{n}{i}=0$

For $n \geq 0$, $\sum_{i=0}^n2^i\binom{n}{i}=3^n$

For $n \geq 0$, $\sum_{i=0}^{\lfloor n/2 \rfloor}\binom{n-1}{i}=f_{n+1}$

For $n \geq 0$, $\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}$