Dgdrxrt

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?

(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)$.

begineqnarray*
kbinomnk= k binomn-1k-1+k binomn-1k.
endeqnarray*
The second term on the right can be rewritten (using the symmetry of binomial coefficients)
begineqnarray*
k binomn-1k= (n-1) binomn-2k-1 =(n-1) binomn-2n-k-1=(n-k) binomn-1n-k=(n-k) binomn-1k-1.
endeqnarray*