Math stuff and other things...but mostly math.: Combanatorics Identity

My blog coder is a piece of junk and won't do binomial notation for combinations (nevermind, I figured it out later), so I'll have to code that part on some other site.

Prove the following combinatorial identity algebraically:

Show that the RHS is equal to the LHS. Use our definition for a combination:

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

And we have to show that ${{n} \choose {k-1}} + {{n} \choose {k}}$ is the same as this. Expand both forms as above.

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

Factor out a n! :

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

Heres where things get tricky. Looking at our definition for $n! = (n)(n-1)(n-2)\cdots (2)(1)$
And $(n-1)! = (n-1)(n-2)\cdots (2)(1)$

Meaning we can rewrite our original as $n! = n(n-1)!$

We can use this to alter each of the fractions to a common base.

$k! = k(k-1)!$
$(k-1)! = \frac{k!}{k}$

And.

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

Substituting the last line of each into our fraction gives us a common base:

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

Add the two:

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

Multiply the n! back in:

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

Remembering our work before:

$(n+1)! = (n+1)(n)(n-1)\cdots (2)(1)$
And:
$n! = (n)(n-1) \cdots (2)(1)$

$(n+1)n! = (n+1)!$

So now we can rewrite it:

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

Which is the expression we were trying to equate it to, JUST AS PLANNED.

This identity can also be explained logically.

Consider some particular object of a group of n + 1 objects, and call it A. Then we can choose k objects which include A in only ${{n} \choose {k-1}}$ ways, because after including A, we must pick k-1 of the remaining n objects.

Also, consider picking k objects from the group which DON'T include A. This can be done in ${{n} \choose {k}}$ ways, because after removing A from our group, we have n objects to choose k amount from.

However, by counting all combinations which do include A and which don't include A, we have counted all possible combinations of picking k objects from a group of n+1 objects, leading to the conclusion that:

JUST. AS. PLANNED.