Return to Answer

Consider $n$ balls in a basket. Let there be $1$ red ball and $n-1$ blue balls. Now look at the number of ways of choosing $r$ balls in two different ways

One way is to choose $r$ balls out of the $n$ balls. So the number of ways is $C(n,r)$

The other way is to look at the cases when out of the $r$ balls chosen if we have a red ball or not. We have only two options namely out of the $r$ balls we could have one red ball or no red balls

The number of ways of having $1$ red ball is to choose the one red ball which can be done in $C(1,1)$ ways and choose the remaining $(r-1)$ balls from the $(n-1)$ blue balls which can be done in $C(n-1,r-1)$ ways

Similarly, the number of ways of having no red balls is to choose all the balls as blue balls which can be done in $C(n-1,r)$ ways

These are the only two cases and these are mutually exclusive and hence the total number of ways is $C(n-1,r-1)+C(n-1,r)$

Hence, we get $$C(n,r) = C(n-1,r-1) + C(n-1,r)$$

The same idea could be extended to prove $C(m+n,r) = \displaystyle \sum_{k=\max(0,r-n)}^{\min(r,m)} C(m,k) C(n,r-k)$.

Consider a basket with $m$ red balls and $n$ blue balls and we want to count the number of ways in which $r$ balls can be drawn. Argue by two different ways to count (sam idea as above) to prove this.

Consider $n$ balls in a basket. Let there be $1$ red ball and $n-1$ blue balls. Now look at the number of ways of choosing $r$ balls in two different ways

One way is to choose $r$ balls out of the $n$ balls. So the number of ways is $C(n,r)$

The other way is to look at the cases when out of the $r$ balls chosen if we have a red ball or not. We have only two options namely out of the $r$ balls we could have one red ball or no red balls

The number of ways of having $1$ red ball is to choose the one red ball which can be done in $C(1,1)$ ways and choose the remaining $(r-1)$ balls from the $(n-1)$ blue balls which can be done in $C(n-1,r-1)$ ways

Similarly, the number of ways of having no red balls is to choose all the balls as blue balls which can be done in $C(n-1,r)$ ways

These are the only two cases and these are mutually exclusive and hence the total number of ways is $C(n-1,r-1)+C(n-1,r)$

Hence, we get $$C(n,r) = C(n-1,r-1) + C(n-1,r)$$

The same idea could be extended to prove a generalization of the above $$C(m+n,r) = \displaystyle \sum_{k=\max(0,r-n)}^{\min(r,m)} C(m,k) C(n,r-k)$$

Consider a basket with $m$ red balls and $n$ blue balls and we want to count the number of ways in which $r$ balls can be drawn. Argue by two different ways to count (same as above) to prove this.

Consider $n$ balls in a basket. Let there be $1$ red ball and $n-1$ blue balls. Now look at the number of ways of choosing $r$ balls in two different ways

One way is to choose $r$ balls out of the $n$ balls. So the number of ways is $C(n,r)$

The other way is to look at the cases when out of the $r$ balls chosen if we have a red ball or not. We have only two options namely out of the $r$ balls we could have one red ball or no red balls

The number of ways of having $1$ red ball is to choose the one red ball which can be done in $C(1,1)$ ways and choose the remaining $(r-1)$ balls from the $(n-1)$ blue balls which can be done in $C(n-1,r-1)$ ways

Similarly, the number of ways of having no red balls is to choose all the balls as blue balls which can be done in $C(n-1,r)$ ways

These are the only two cases and these are mutually exclusive and hence the total number of ways is $C(n-1,r-1)+C(n-1,r)$

Hence, we get $$C(n,r) = C(n-1,r-1) + C(n-1,r)$$

Consider $n$ balls in a basket. Let there be $1$ red ball and $n-1$ blue balls. Now look at the number of ways of choosing $r$ balls in two different ways

One way is to choose $r$ balls out of the $n$ balls. So the number of ways is $C(n,r)$

The other way is to look at the cases when out of the $r$ balls chosen if we have a red ball or not. We have only two options namely out of the $r$ balls we could have one red ball or no red balls

The number of ways of having $1$ red ball is to choose the one red ball which can be done in $C(1,1)$ ways and choose the remaining $(r-1)$ balls from the $(n-1)$ blue balls which can be done in $C(n-1,r-1)$ ways

Similarly, the number of ways of having no red balls is to choose all the balls as blue balls which can be done in $C(n-1,r)$ ways

These are the only two cases and these are mutually exclusive and hence the total number of ways is $C(n-1,r-1)+C(n-1,r)$

Hence, we get $$C(n,r) = C(n-1,r-1) + C(n-1,r)$$

The same idea could be extended to prove $C(m+n,r) = \displaystyle \sum_{k=\max(0,r-n)}^{\min(r,m)} C(m,k) C(n,r-k)$.

Consider a basket with $m$ red balls and $n$ blue balls and we want to count the number of ways in which $r$ balls can be drawn. Argue by two different ways to count (sam idea as above) to prove this.

Consider $n$ balls in a basket. Let there be $1$ red ball and $n-1$ blue balls. Now look at the number of ways of choosing $r$ balls.

Consider $n$ balls in a basket. Let there be $1$ red ball and $n-1$ blue balls. Now look at the number of ways of choosing $r$ balls in two different ways

One way is to choose $r$ balls out of the $n$ balls. So the number of ways is $C(n,r)$

The other way is to look at the cases when out of the $r$ balls chosen if we have a red ball or not. We have only two options namely out of the $r$ balls we could have one red ball or no red balls

The number of ways of having $1$ red ball is to choose the one red ball which can be done in $C(1,1)$ ways and choose the remaining $(r-1)$ balls from the $(n-1)$ blue balls which can be done in $C(n-1,r-1)$ ways

Similarly, the number of ways of having no red balls is to choose all the balls as blue balls which can be done in $C(n-1,r)$ ways

These are the only two cases and these are mutually exclusive and hence the total number of ways is $C(n-1,r-1)+C(n-1,r)$

Hence, we get $$C(n,r) = C(n-1,r-1) + C(n-1,r)$$