Friday, January 3, 2020

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...