Consider the identity kC(n,k) = nC(n-1,k-1) where 1 <= k <= n, provy the identity by induction on n, using Pascal's identity

Question

I've tried looking everywhere to get a clear understanding of the answer, however I am at a loss. The book says if n=1 then k=1. Assume the identity is true for n-1 we will shot it for n. If k=n, then both sides equal n. Otherwise k ≤ n-1.

kC(n,k) = k(C(n-1,k) + C(n-1,k-1))

=kC(n-1,k) + (k-1)C(n-1,k-1)+C(n-1,k-1)

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

=(n-1)[C(n-2,k-1)+C(n-2,k-2)]+C(n-1,k-1)

(this isn't complete because I get how they get nC(n-1,k-1))

Anyway, I understand the first two rows. However for the last two I don't know where the (n-1), (n-2),(k-2) parts came from.

Sorry if I'm wrong about this part, but is the reason for replacing k with (n-1) because k = n-1?

Answer 1

(I know you asked for induction, but I can never resist a combinatorial proof.)

Suppose you have $n$ people and want to form a committee of $k$ people with president. We can do this in two different ways.

One way is to first form a committee without a president, which can be done in $C(n,k)$ ways. Out of the chosen $k$ people, select one of them to be the president. From this perspective, there are $k C(n,k)$ ways to form the committee.

Another way is to first select a president out of all $n$ people. Now that you have a president, choose an additional $k-1$ people to serve on the committee out of the remaining $n-1$ people, which can be done in $C(n-1,k-1)$ ways. From this perspective, there are $nC(n-1,k-1)$ ways to form the committee.

Since the two expressions enumerate the same object, we conclude that $kC(n,k) = nC(n-1,k-1)$.

Answer 2

\begin{eqnarray*} k\binom{n}{k}= k \binom{n-1}{k-1}+k \binom{n-1}{k}. \end{eqnarray*} The second term on the right can be rewritten (using the symmetry of binomial coefficients) \begin{eqnarray*} k \binom{n-1}{k}= (n-1) \binom{n-2}{k-1} =(n-1) \binom{n-2}{n-k-1}=(n-k) \binom{n-1}{n-k}=(n-k) \binom{n-1}{k-1}. \end{eqnarray*}