Simplify $\binom nr+ 4\binom n{r+1} + 6\binom n{r+2} + 4\binom n{r+3}+\binom n{r+4}$

Question

For $$4\le r \le n,$$ $${n \choose r}+4{n \choose {r+1}}+6{n \choose {r+2}}+4{n \choose {r+3}}+{n \choose {r+4}}$$ equals 1. $${n+4}\choose{r+4}$$ 2.$${n+4}\choose{r}$$ 3.$${n+3}\choose{r-1}$$ 4.$${n+4}\choose{r+3}$$

I have no idea to solve this one. Would be grateful to anyone who helps. Thank you.

Answer 1

Vandermonde's identity is useful, but I will demonstrate combinatorially. Given formula can be represented as $$ \binom{4}{4}\binom{n}{r}+\binom{4}{3}\binom{n}{r+1}+\binom{4}{2}\binom{n}{r+2}+\binom{4}{1}\binom{n}{r+3}+\binom{4}{0}\binom{n}{r+4}. $$ Let $S=\{1,2,\cdots, n,n+1,n+2,n+3,n+4\}$ and its subset $T=\{n+1,n+2,n+3,n+4\}$. First, you can select $r+4$ elements of $S$ without repetition. Then the number of possiblities is $\binom{n+4}{r+4}$. Now select $r+4-k$ elements of $S\setminus T$ and $k$ elements of $T$ (still selecting $r+4$ elements of $S$), where $0\le k \le 4$. Then by multiplication rule, the number of possiblities is $\binom{n}{r+4-k}\binom{4}{k}$. Since $k$ can be $0,1,2,3,4$, we get $$ \binom{n+4}{r+4}=\binom{4}{4}\binom{n}{r}+\binom{4}{3}\binom{n}{r+1}+\binom{4}{2}\binom{n}{r+2}+\binom{4}{1}\binom{n}{r+3}+\binom{4}{0}\binom{n}{r+4}. $$

Answer 2

Now, note that $$\binom{n}{r}+\binom{n}{r+1}=\binom{n+1}{r+1}$$

Note that $$\binom{n}{r}+\binom{n}{r+1}+\binom{n}{r+1}+\binom{n}{r+2}=\binom{n+1}{r+1}+\binom{n+1}{r+2}=\binom{n+2}{r+2} $$

Then, $$\binom{n+1}{r+1}+3\binom{n+1}{r+2}+3\binom{n+1}{r+3}+\binom {n+1}{r+4}=\binom{n+1}{r+1}+\binom{n+1}{r+2}+2(\binom{n+1}{r+2}+\binom{n+1}{r+3})+\binom{n+1}{r+3}+\binom {n+1}{r+4}=\binom{n+2}{r+2}+2\binom{n+2}{r+3}+\binom{n+2}{r+4}=\binom{n+4}{r+4}$$.

Note that $${n \choose r}+4{n \choose {r+1}}+6{n \choose {r+2}}+4{n \choose {r+3}}+{n \choose {r+4}}=({n \choose r}+3{n \choose {r+1}}+3{n \choose {r+2}}+{n \choose {r+3}})+({n \choose {r+1}}+3{n \choose {r+2}}+3{n \choose {r+3}}+{n \choose {r+4}})=\binom{n+3}{r+3}+\binom{n+3}{r+4}=\binom{n+4}{r+4}$$.

The answer is $1$.

Answer 3

We have, $${n \choose r}+{n \choose r-1}={n+1 \choose r}$$ In, $${n \choose r}+4{n \choose {r+1}}+6{n \choose {r+2}}+4{n \choose {r+3}}+{n \choose {r+4}}$$ $${n \choose r+4} + {n \choose r+3} = {n+1 \choose r+4}$$ $$3{n \choose r+3} + 3{n \choose r+2} = 3{n+1 \choose r+3}$$ $$3{n \choose r+2} + 3{n \choose r+1} = 3{n+1 \choose r+2}$$ $${n \choose r+1} + {n \choose r} = {n+1 \choose r+1}$$ Thus, using similar steps, $${n \choose r}+4{n \choose {r+1}}+6{n \choose {r+2}}+4{n \choose {r+3}}+{n \choose {r+4}}={n+1 \choose r+4}+3{n+1 \choose r+3}+3{n+1 \choose r+2}+{n+1 \choose r+1}={n+2 \choose r+4}+2{n+2 \choose r+3}+{n+2 \choose r+2}={n+3 \choose r+4}+{n+3 \choose r+3}={n+4 \choose r+4}$$

Answer 4

Vandermonde's Identity says $$ \sum_{k=0}^4\binom{4}{4-k}\binom{n}{r+k}=\binom{n+4}{r+4} $$

Answer 5

Hint: Break your sum as follows: $${n \choose r}+4{n \choose {r+1}}+6{n \choose {r+2}}+4{n \choose {r+3}}+{n \choose {r+4}}$$= $$[{n \choose r}+{n \choose {r+1}}]+[3{n \choose {r+1}}+3{n \choose {r+2}}]+[3{n \choose {r+2}}+3{n \choose {r+3}}]+[{n \choose {r+3}}+{n \choose {r+4}}]$$ Using the fact that $$\binom{n}{r}+\binom{n}{r+1}=\binom{n+1}{r+1}$$, This becomes: $${n+1 \choose r+1}+3{n+1 \choose r+2}+3{n+1 \choose r+3}+{n+1 \choose r+4}$$ Now can you do something similar again?

Answer 6

Using Vandermonde's Identity,

$$\sum_{s=0}^4\binom 4s\binom n{r+s}=\sum_{s=0}^4\binom 4{4-s}\binom n{r+s}=\binom {n+4}{r+4}\qquad\blacksquare$$