Prove that, $\binom{3n}{r}=\binom{3n-1}{r} + \binom{3n-1}{r-1}$

Question

Reading through my textbook I came across the following problem and I am looking for some help solving it.

Prove that,

$$\binom{3n}{r}=\binom{3n-1}{r} + \binom{3n-1}{r-1}$$

In a previous problem I solved the following but I wasn't sure how to use it to prove the question above. Prove,

$$\binom{n}{r}=\binom{n}{n-r}$$

Solution:

left Side,

$$\binom{n}{r}=\frac{n!}{(n-r)!r!}$$

right side,

$$\binom{n}{n-r}=\frac{n!}{(n-(n-r))!(n-r)!} = \frac{n!}{(n-r)!r!}$$

Therefore completing the proof,

but how do I solve my first question? thanks!

Answer 1

You should develop the binomial:

$${3n\choose r} = \frac{(3n)!}{(3n-r)!r!} = \frac{3n}{3n-r}{3n-1\choose r}$$

Develop $\frac{3n}{3n-r}$ trying to find $1+x$:

$${3n\choose r} = \left(1+\frac{r}{3n-r}\right){3n-1\choose r}={3n-1\choose r}+\frac{r}{3n-r}{3n-1\choose r}$$

Finally, developing second binomial, you can find:

$${3n\choose r} = {3n-1\choose r}+\frac{r}{3n-r}\frac{(3n-1)!}{r!(3n-1-r)!} = {3n-1\choose r} + \frac{(3n-1)!}{(r-1)!(3n-r)!}$$

Obtaining the final result:

$$ = {3n-1\choose r} + {3n-1\choose r-1}$$

Answer 2

You can use the general case, also $${k+t \choose k}+{k+t \choose k-1}={k+t+1 \choose k} $$

Proof: $${k+t \choose k}+{k+t \choose k-1}=\frac{(k+t)!}{k!.t!}+\frac{(k+t)!}{(k-1)!(t+1)!}=\frac{(k+t)!}{k.(k-1)!.t!}+\frac{(k+t)!}{(t+1)(k-1)!(t)!}$$ $$=\frac{(k+t)!}{(k-1)!.t!}\bigg(\frac{1}{k}+\frac{1}{t+1} \bigg)=\frac{(k+t+1)! }{k!(t+1)!}={k+t+1 \choose k}.$$

Take $k+t=3n$ and $k=r$, that's your case