Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do you solve this?

Find out which recurrence relation involving $\dbinom{n}{r}$ is valid, and thus prove that we can compute $\dbinom{n}{r}$ in a recursive manner.

I appreciate any help. Thank You

share|improve this question
1  
Is $C(n,r)$ the binomial coefficient? Most of us here are more accustomed to writing it as $\dbinom{n}{r}$... –  J. M. May 9 '12 at 18:12
    
@J.M. - Yes, the binomial coefficient - I don't know how to fix it though :\ –  Adel May 9 '12 at 18:14
1  
I don't quite get it, do you want to prove $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$? –  Gigili May 9 '12 at 18:20
    
@Gigili - OK I need to update my question - Thank You Very Much –  Adel May 9 '12 at 18:26
    
You know Pascal's triangle, I presume? –  J. M. May 9 '12 at 18:31

3 Answers 3

up vote 3 down vote accepted

There are many recurrence relations for $\dbinom{n}{r}$. One of the most commonly used one is the following. $$\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}.$$ There are many ways to prove this and one simple way is to look at $\displaystyle (1+x)^{n+1}$. We know that $$(1+x)^{n+1} = (1+x)^{n} (1+x).$$ Now compare the coefficient of $x^r$ on both sides.

The left hand the coefficient of $x^r$ is $$\dbinom{n+1}{r}.$$ On the right hand side, the $x^r$ term is obtained by multiplying the $x^r$ term of $(1+x)^n$ with the $1$ from $(1+x)$ and also by multiplying the $x^{r-1}$ term of $(1+x)^n$ with the $x$ from $(1+x)$. Hence, the coefficient of $x^r$ is given by the sum of these two terms from the right hand side i.e. $$\dbinom{n}{r} + \dbinom{n}{r-1}$$ enter image description here As Rob and J.M have pointed out, these recurrences define the celebrated Pascal's triangle. A pictorial representation is shown above. Each row represents the value of $n$ starting from $0$. On a row, as we proceed from left to right, the different values of $r$ from $0$ to $n$ are hit. The arrows indicate how the $r^{th}$ value on the $(n+1)^{th}$ row is obtained as the sum of the $(r-1)^{th}$ and $r^{th}$ value on the $n^{th}$ row.

share|improve this answer
1  
It might be useful to mention that that recurrence defines Pascal's Triangle. –  robjohn May 9 '12 at 18:32
    
@robjohn Right. I was trying to draw a diagram of the Pascal's triangle. I will update the post soon. –  user17762 May 9 '12 at 18:38
    
@J.M. Thanks. I was not aware of \dbinom. –  user17762 May 9 '12 at 18:42
    
No worries; I learned it rather recently, too. –  J. M. May 9 '12 at 18:44

To prove: $$\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}$$

We have: $$\dbinom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-k-1)!}\frac{1}{n-k}$$

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

Adding the two together:

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

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

$$=\dbinom{n}{k}$$

share|improve this answer
    
Thank You So Much Gigi! –  Adel May 9 '12 at 20:35

From the familiar $\binom{n}{r}=\frac{n!}{r!(n-r)!}$, you can readily derive the formula $$\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}.$$ This can be computationally and theoretically useful, particularly when we are interested in the expression $$\binom{n}{r}p^r(1-p)^{n-r}$$ that comes up when we are working with the Binomial Distribution.

share|improve this answer
1  
Or $$\binom{n}{r}=\frac{n}{n-r}\binom{n-1}{r}$$ which may be quicker if $2r \gt n$ –  Henry May 9 '12 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.