Combinatorial proof of the basic additive identity
Here we are going to choose a specific example, but there
is nothing magical about the numbers chosen. The general proof would use
n instead of 19, n-1 instead of 18, k instead of 6 and k-1 instead of 5.
How many ways are there to choose 6 things out of 19? Let's
call one of the things thing19, and consider that if we pick 6
things, either our selection will have thing19 or it won't.
Selections with thing19: Here we need 5 more things
out of the 18 remaining to get a total of 6 things. Selections without thing19: Here we need 6 more things
out of the 18 remaining to get a total of 6 things.
Every selection with thing19 has to be different from the
selections without thing19, so we have now numbered all the
selections of 6 things out of 19 in
terms of 6 things out of 18 and 5 things out of 18. Using our symbols
for the binomial coefficients, we get
Which as we stated above in italics is just a specific case of
an easily generalized principle.
