How do we prove that #((n),(k))=sum_(l=k)^n((l-1),(k-1))#?
1 Answer
Use the identity
Explanation:
Recall the identity
To prove this as
=
#(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-1),(k-1))=((n-2),(k-1))+((n-2),(k-2))#
Hence
Now similarly split
#((n-2),(k-2))=((n-3),(k-2))+((n-3),(k-3))# and
Going on similarly, we get