Proving an Combination formula $ \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$ Proving an Combination formula $\displaystyle \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$
$\bf{My Try}$::$\displaystyle{\binom{n-1}{k}+\binom{n-1}{k-1}=}$
$\displaystyle{\frac{\left(n-1\right)!}{k!\left(n-k-1\right)!}+\frac{\left(n-1\right)!}{\left(k-1\right)!\left(n-k\right)!}=}$
$\displaystyle{\frac{\left(n-1\right)!}{k\,\left(k-1\right)!\left(n-k-1\right)!}+\frac{\left(n-1\right)!}{\left(k-1\right)!\left(n-k-1\right)!\,\left(n-k\right)}}=$
$\displaystyle \frac{(n-1)!}{(k-1)!\cdot (n-k-1)!}\left(\frac{1}{k}+\frac{1}{n-k}\right) = \binom{n}{k}$
My Question is How can i prove using combinational argument
Help Required
Thanks
 A: Given $n$ people we can form a committee of size $k$ in ${n\choose k}$ ways. We can count the same thing by counting the number of ways in which person $x$ is in the committee and person $x$ is not in the committee. The number of ways person $x$ is not in the committee is ${n-1\choose k}$. We have $n-1$ people to work with because we are excluding the possibility of person $x$ being in the committee. The number of ways person $x$ is in the committee is ${n-1\choose k-1}$. We have $n-1$ people to work with since person $x$ is in the committee by default and we choose $k-1$ people because person $x$ is in the committee. Thus ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$.
A: A bitstring is a string of zeros and ones. Answer the following questions. For the first three questions, express your answer in the form of a binomial coefficient.
(A) What is the number of bitstrings of length $n$ containing exactly $k$ ones?
(B) What is the number of bitstrings of length $n$ containing exactly $k$ ones and starting with a zero?
(C) What is the number of bitstrings of length $n$ containing exactly $k$ ones and starting with a one?
(D) Do you see why the answer to (A) is the sum of the answers to (B) and (C)?
A: Let $S$ have $n$ elements, and we are trying to find the number of subsets with $k$ elements. Choose some $a \in S$.  We will count the number of subsets with $a$ of size $k$ and without $a$ of size $k$, then add them together.
For the first, observe that there are $n-1 \choose k-1$ ways to do this (since $a$ doesn't have to be chosen because we know we're going to include it, and there are $n-1$ elements left to choose from).
Second, we have $n-1$ elements and we're choosing a $k$-set.  There are $n-1 \choose k$ ways to do this.
And we're done..
