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

  • 1
    Is $C(n,r)$ the binomial coefficient? Most of us here are more accustomed to writing it as $\dbinom{n}{r}$...2012-05-09
  • 0
    @J.M. - Yes, the binomial coefficient - I don't know how to fix it though :\2012-05-09
  • 1
    I don't quite get it, do you want to prove $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$?2012-05-09
  • 0
    @Gigili - OK I need to update my question - Thank You Very Much2012-05-09
  • 0
    You know Pascal's triangle, I presume?2012-05-09
  • 0
    @J.M. - Yes, but I must solidify my friendship with that neat triangle2012-05-09

3 Answers 3

3

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

5

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.

  • 1
    Or $$\binom{n}{r}=\frac{n}{n-r}\binom{n-1}{r}$$ which may be quicker if $2r \gt n$2012-05-09
4

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.

  • 2
    It might be useful to mention that that recurrence defines [Pascal's Triangle](http://en.wikipedia.org/wiki/Pascal%27s_triangle).2012-05-09
  • 0
    @robjohn Right. I was trying to draw a diagram of the Pascal's triangle. I will update the post soon.2012-05-09
  • 0
    @J.M. Thanks. I was not aware of `\dbinom`.2012-05-09
  • 0
    No worries; I learned it rather recently, too.2012-05-09