Proving an Combination formula $ \binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}$ [duplicate]

Question

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

Answer 1

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}$.

Answer 2

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)?

Answer 3

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..