Sunday, November 17, 2019

algebra precalculus - Simplify the expression $binom{n}{0}+binom{n+1}{1}+binom{n+2}{2}+cdots +binom{n+k}{k}$


Simplify the expression $\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k}{k}$


My attempt: Using the formula $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$


$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots \binom{n+k-1}{k-1}+\binom{n+k}{k}$



=$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +\binom{n+k-1}{k-1}+(\binom{n+k-1}{k}+\binom{n+k-1}{k-1})$


=$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\cdots +2\binom{n+k-1}{k-1}+\binom{n+k-1}{k}$


I can again use the same formula for the term $2\binom{n+k-1}{k-1}$, and in the next to step to the term $3\binom{n+k-2}{k-2}$.


But I don't think this way the expression will get simplified.


Any help is appreciated.


Answer



First show that $\large{n\choose r}={{n-1}\choose {r-1}}+{{n-1}\choose r}$,


from which we get $\large{{n+r+1}\choose r}={{n+r}\choose r}+{{n+r}\choose {r-1}}$


By the same rule, $\large{{n+r}\choose {r-1}}={{n+r-1}\choose {r-1}}+{{n+r-1}\choose {r-2}}$


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



$..$ $\quad \quad \quad \quad ..$ $ \quad \quad \quad ..$


$..$ $\quad \quad \quad \quad ..$ $ \quad \quad \quad ..$


$..$ $\quad \quad \quad \quad ..$ $ \quad \quad \quad ..$


$\large{{n+3}\choose {2}}={{n+2}\choose {2}}+{{n+2}\choose {1}}$


$\large{{n+2}\choose {1}}={{n+1}\choose {1}}+{{n+1}\choose {0}}$


Adding, we get $\large{n\choose 0}+{{n+1}\choose 1}+...+{{n+r-1}\choose {r-1}}+{{n+r}\choose r}={{n+r+1}\choose r}$



Alternatively, we can fix any $r$ of the $(n+r+1)$ objects given. Label them $A_1,A_2,...A_r$. Now our choices of $r$ objects from the $(n+r+1)$ objects may or may not contain any or all of the set $\{A_1,A_2,...,A_r\}$.


Case I: It does not contain $A_1$


This will happen in $\large{{n+r}\choose r}$ ways as the $r$ things have to be chosen from the remaining $(n+r)$ things.


Case II: It contains $A_1$ but does not contain $A_2$.



This will happen in $\large{{n+r-1}\choose {r-1}}$ ways, because having chosen $A_1$ and rejectd $A_2$, we have only $(n+r-1)$ things to choose from and we need only $(r-1)$.


$...$


Case r: It contains $A_1,A_2,...,A_{r-1}$ but does not contain $A_r$.


This will happen in $\large {{n+1}\choose 1}$ ways.


Case $(r+1)$: It contains $A_1,A_2,...,A_r$.


This will happen in $\large{n\choose 0}=1$ way.


Hence, $\displaystyle\sum_{k=0}^{r}{{n+k}\choose k}={{n+r+1}\choose r}$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...