# Falling Factorial

Definition of Combination:
$\displaystyle \boxed { {_n}C_k = \frac {n!}{k!(n-k)!} = \binom{n}{k} }$

Example:
$\displaystyle {_5}C_3 = \frac {5!}{3!(5-3)!} = \frac {5!}{3!2!} = \frac {5.4.3.2.1}{3.2.1.2.1} = \frac {5.4.3}{3.2.1} = \binom{5}{3}$

Combinations are even simpler to write with ‘Falling Factorial’ $x^{\underline {n}}$

$\boxed { x^{\underline {n}} = \underbrace {(x-0)(x-1)(x-2)... (x-(n-1))}_{n factors} }$

Example:
$5^{\underline {5}} = \underbrace {(5-0)(5-1)(5-2)... (5-(5-1))}_{5 \: factors} = 5.4.3.2.1= 5!$
$\boxed { n^{\underline {n}} = n! }$

$(2n)^{\underline {n+1}} = \underbrace {(2n). (2n-1). (2n-2).... (2n-(n-1)).(2n-(n))}_{(n+1) \: terms}$

$(2n)^{\underline {n+1}} = \underbrace {(2n). (2n-1). (2n-2).... (n+1)}_{(n)\: terms}.(n)$

$\boxed { (2n)^{\underline {n+1}} = (2n)^{\underline {n}}.(n) }$

$\displaystyle \binom{n}{k} = \frac {n!}{k!(n-k)!} = \frac {(n-0).(n-1)... (n-(k-1))} { (k-0).(k-1)... (k-(k-1)) } = \frac { n^{\underline {k}}} {k^{\underline {k}}}$

$\displaystyle \boxed { \binom{n}{k} = \frac { n^{\underline {k}}} {k^{\underline {k}}} }$

$\text {Prove:} \binom {2n}{n} - \binom {2n}{n+1} = \frac {1}{n+1} \binom {2n}{n}$

$\text {Proof:}$

$\binom {2n}{n} - \binom {2n}{n+1} = \frac {(2n)^{\underline {n}}} {n^{\underline {n}}} - \frac {(2n)^{\underline {n+1}}} {(n+1)^{\underline {n+1}}}$

$= \frac {(2n)^{\underline {n}}} {n^{\underline {n}}} - \frac {(2n)^{\underline {n}}(n)} {(n+1)!}$

$= \frac {(2n)^{\underline {n}}} {n^{\underline {n}}} - \frac {(2n)^{\underline {n}}(n)} {(n+1).(n)^{\underline {n}} }$ [since (n+1)! = (n+1).n! ]

$= \frac {(n+1).(2n)^{\underline {n}} - (2n)^{\underline {n}}(n) } {(n+1).(n)^{\underline {n}} }$

$= \frac {(n+1-n).(2n)^{\underline {n}} } {(n+1).(n)^{\underline {n}} }$

$= \frac {1}{n+1} \frac {(2n)^{\underline {n}}} {(n)^{\underline {n}} }$

$\boxed{ \binom {2n}{n} - \binom {2n}{n+1} = \frac {1}{n+1} \binom {2n}{n} }$

Ref: “The Math Girls

Advertisements