Binomial coefficient proof

Question

Prove that for any $0\lt r\lt n$ we have $$\binom nr=\binom{n-1}{r-1}+\binom{n-1}r.$$

How do prove this and what step do i take in order for it to be true?

Answer 1

This is simple. $(_r^n)$ corresponds to the number in the $(r+1)$th position of the $(n+1)$th row of pascal's triangle. Pascal's triangle is generated by, for each position, adding the numbers in the positions above it, which happen to be $(_{r-1}^{n-1})$ and $(_r^{n-1})$.

Answer 2

Ooh, one of those binomial coefficient questions that can be answered by giving a small story. I like those.

The concept to think about in this case is that of a bowl filled with $n$ balls and one of those $n$ balls is coloured pink, while the rest ($n-1$ in total) is just plain, boring white. If you take $r$ balls from this bowl, either the pink ball is one of those (in $\binom{n-1}{r-1}$ cases; can you see why?) or it isn't (in $\binom{n-1}{r}$ cases).

Answer 3

By definition, the inomial coefficient $n\choose k$ is the coeffient of $x^k$ in the expansion of the binomial $(1+x)^n$. From $$(1+x)^n=(1+x)^{n-1}\cdot (1+x)=(1+x)^{n-1} + x\cdot(1+x)^{n-1}$$ (for $n\ge 1$) we see that the coefficient of $x^r$ in $(1+x)^r$ is the sum of the coefficients of $x^{r}$ and of $x^{r-1}$ in $(1+x)^{n-1}$, in other words $$ {n\choose r}={n-1\choose r}+{n-1\choose r-1}.$$

Answer 4

Suppose you have a group of $n-1$ boys. You want to select $r-1$ or $r$ boys out of them.

You are too lazy to write $$\binom{n-1}{r-1}+\binom{n-1}{r}$$

So, you take Justin Bieber and put him with the $n-1$ boys and then select $r$ people.

$$\binom{n}{r}$$ If Justin Bieber comes up in your list, you can claim that he is not a guy you selected $r-1$ boys. If he doesn't, well, you selected $r$ boys.