the binomial theorem the Question: Prove the critical Lemma we need to complete the proof of the Binomial Theorem: 
i.e. prove $(^{n}_{k})=(^{n-1}_{k-1})+(^{n-1}_{k})$ for $0\lt k\lt n$ (this formula is known as Pascal’s Identity) 
you can do this by a direct proof without using Induction. 
Any help appreciated, I have no idea what it's talking about 
 A: Hint:  Think about what $\binom{n}{k}$ means combinatorially.  
Choose any one of the $n$ total elements at random.  There are two cases:  Either the element we have chosen is amongst the $k$-element subset, or it is not.
This method requires far less effort than non-combinatorial proofs, and a complete solution of this form can be found here:
http://www.math.uvic.ca/faculty/gmacgill/guide/combargs.pdf
A: Recall that 
$${a \choose b}=\frac{a!}{b!(a-b)!}$$
and (for integer a)
$$a!=\prod_{k=1}^ak=a\times(a-1)\times(a-2)\times\cdots\times1$$
Starting from the right hand side
$${n-1 \choose k-1}+{n-1 \choose k}=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}=\frac{(n-1)!k+(n-1)!(n-k)}{k!(n-k)!}\\=\frac{(n-1)!(n-k+k)}{k!(n-k)!}=\frac{(n-1)!n}{k!(n-k)!}$$
Can you take it from here?
A: $\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-1-k)!}=\frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{1}{k}+\frac{1}{n-k}\right)$
$=\frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{n-k+k}{k(n-k)}\right)=\frac{(n-1)!}{(k-1)!(n-k-1)!}\frac{n}{k(n-k)}=\frac{(n-1)!.n}{(k-1)!.k.(n-k-1)!.(n-k)}=\frac{n!}{k(n-k)!}$
