3
$\begingroup$

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

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

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.

$\endgroup$
  • 2
    $\begingroup$ It might be useful to mention that that recurrence defines Pascal's Triangle. $\endgroup$ – robjohn May 9 '12 at 18:32
  • $\begingroup$ @robjohn Right. I was trying to draw a diagram of the Pascal's triangle. I will update the post soon. $\endgroup$ – user17762 May 9 '12 at 18:38
  • $\begingroup$ @J.M. Thanks. I was not aware of \dbinom. $\endgroup$ – user17762 May 9 '12 at 18:42
  • $\begingroup$ No worries; I learned it rather recently, too. $\endgroup$ – J. M. is a poor mathematician May 9 '12 at 18:44
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Or $$\binom{n}{r}=\frac{n}{n-r}\binom{n-1}{r}$$ which may be quicker if $2r \gt n$ $\endgroup$ – Henry May 9 '12 at 18:55
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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