Let m and w be positive integers Give a combinatorial argume

Let m and w be positive integers. Give a combinatorial argument to prove that for integers k ? 0,
SUM(from j=0 to k) C(m, j)*C(w, k-j) = C(m+w, k)

Solution

Let m and w be positive integers. Give a combinatorial argument to prove that for integers k ? 0,
SUM(from j=0 to k) C(m, j)*C(w, k-j) = C(m+w, k)

CONSIDER 2 BASKETS OF FRUITS SAY ONE BASKET HAVING \"M\" NUMBER OF APPLES AND ANOTHER BASKET CONTAINING \"W\" NUMBER OF STRAW BERRIES , WITH BOTH M & W BEING POSITIVE INTEGERS ..LET THE FRUITS BE ALSO NUMBERED AS M1,M2,M3.....,MM ....AND ....W1,W2,W3, .....WW SO THAT THEY REMAIN DISTINCT FROM ONE ANOTHER ....

...... NOW SUPPOSE WE WANT TO MAKE A COLLECTION OF K DISTINCT FRUITS FROM BOTH BASKETS ...WE CAN DO THIS IN 2 WAYS ..

1...TAKE \" J \" NUMBER OF FRUITS FROM FROM BASKET ONE AND THEN TAKE THE REST OF \"( K - J ) \" FRUITS FROM BASKET 2 ...MAKING A TOTAL J FRUITS ....

IN THIS WAY ....IF WE TAKE ..

i)...J=0 FROM B1 & J=K FROM B2 , WE HAVE ...C[M,0]*C[W,K]...COMBINATIONS

ii)...J=1 FROM B1 & J=K-1 FROM B2 , WE HAVE ...C[M,1]*C[W,K-1]...COMBINATIONS

iii).....J=2 FROM B1 & J=K-2 FROM B2 , WE HAVE ...C[M,2]*C[W,K-2].COMBINATIONS

....ETC....TILLL.....

FOR ..J=K FROM B1 & J=0 FROM B2 , WE HAVE ...C[M,K]*C[W,0]...COMBINATIONS

=================

ADDING THEM ALL WE GET THE TOTAL NUMBER OF COMBINATIONS AS ....

C[M,0]*C[W,K] +C[M,1]*C[W,K-1] + C[M,2]*C[W,K-2]+....+ C[M,K]*C[W,0]

= SUM(from j=0 to k) [ C(m, j)*C(w, k-j)] ....THE LEFT SIDE OF THE GIVEN EQN. TO BE PROVED ..

NOW WE CAN DO THE SAME BY ANOTHER METHOD ...NAMELY ..

COMBINE THE 2 BASKETS OF FRUITS IN TO ONE AND SELECT K FRUITS FROM THE TOTAL OF M+W FRUITS ...THIS CAN BE DONE IN ..C [ M+W , K ] WAYS ..

OBVIOUSLY SINCE BOTH METHODS RESULT IN THE SAME OUT COME THEIR VALUES SHALL BE EQUAL ...SO WE CONCLUDE THAT ...

SUM(from j=0 to k) [ C(m, j)*C(w, k-j)] . = C[ M+W , K ]