Question

How do we prove that `((n),(k))=sum_(l=k)^n((l-1),(k-1))`?

Answer 1

Use the identity `((n),(k))=((n-1),(k))+((n-1),(k-1))`. See below for details.

Explanation:

Recall the identity `((n),(k))=((n-1),(k))+((n-1),(k-1))`

To prove this as `((n),(k))=(n!)/(k!(n-k)!)`

=`(nxx(n-1)!)/(kxx(k-1)!(n-k)(n-k-1)!)`

=`((n-1)!)/((k-1)!(n-k-1)!)[n/(k(n-k))]`

=`((n-1)!)/((k-1)!(n-k-1)!)[((n-k)+k)/(k(n-k))]`

=`((n-1)!)/((k-1)!(n-k-1)!)[1/k+1/(n-k)]`

=`((n-1)!)/(k(k-1)!(n-k-1)!)+((n-1)!)/(k(k-1)!(n-k)(n-k-1)!)`

=`((n-1)!)/(k!(n-k-1)!)+((n-1)!)/(k!(n-k)!)=((n-1),(k))+((n-1),(k-1))`

Hence `((n),(k))=((n-1),(k))+((n-1),(k-1))`, bur from this we get

`((n-1),(k-1))=((n-2),(k-1))+((n-2),(k-2))`

Hence `((n),(k))=((n-1),(k))+((n-2),(k-1))+((n-2),(k-2))`

Now similarly split `((n-2),(k-2))` into

`((n-2),(k-2))=((n-3),(k-2))+((n-3),(k-3))` and

`((n),(k))=((n-1),(k))+((n-2),(k-1))+((n-3),(k-2))+((n-3),(k-3))`

Going on similarly, we get

`((n),(k))=sum_(l=k)^n((l-1),(k-1))`