Originally Posted by

**oldguynewstudent** Attached is the section on Combinatorial Proofs from my text. I am a little confused. I understand the proof of the special case, then it goes on to say "It is no harder to prove in general."

I would prove this identity in the following manner but I'm not sure if the following is a combinatorial proof or not. Please let me know if it is, or if it is not a combinatorial proof, please point me to a resource so I will understand it better.

Prove the identity: $\displaystyle (n)_{k}=(n-1)_{k}+k*(n-1)_{k-1}$

LHS $\displaystyle (n)_{k}=\frac{n!}{(n-k)!}$

RHS $\displaystyle (n-1)_{k}+k*(n-1)_{k-1}=\frac{(n-1)!}{(n-1-k)!}+\frac{k*(n-1)!}{(n-1-k+1)!}=$

$\displaystyle \frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)!}=\frac{(n-1)!}{(n-k-1)!}+\frac{k*(n-1)!}{(n-k)(n-k-1)!}=$

$\displaystyle \frac{(n-k)(n-1)!+k*(n-1)!}{(n-k)(n-k-1)!}=\frac{(n-k+k)(n-1)!}{(n-k)!}=\frac{n(n-1)!}{(n-k)!}=\frac{n!}{(n-k)!}$

Since the LHS equals the RHS this completes the proof.

Please let me know if the above is a combinatorial proof or not.