2022-10-22

Prove that $\sum _{k=0}^{m}\frac{\left(\genfrac{}{}{0}{}{m}{k}\right)}{\left(\genfrac{}{}{0}{}{n}{k}\right)}=\frac{n+1}{n+1-m}$

Do you have a similar question?

Kason Gonzales

Expert

Step 1
You can solve your problem by following these steps:
1) First show that
$\frac{\left(\genfrac{}{}{0}{}{m}{k}\right)}{\left(\genfrac{}{}{0}{}{n}{k}\right)}=\frac{\left(\genfrac{}{}{0}{}{n-k}{m-k}\right)}{\left(\genfrac{}{}{0}{}{n}{m}\right)}.$
2) Now show that
$\left(\genfrac{}{}{0}{}{n}{m}\right)\cdot \frac{n+1}{n+1-m}=\left(\genfrac{}{}{0}{}{n+1}{m}\right).$
3) Use steps 1 and 2 to prove that the equation you require is equivalent to proving
$\sum _{k=0}^{m}\left(\genfrac{}{}{0}{}{n-k}{m-k}\right)=\left(\genfrac{}{}{0}{}{n+1}{m}\right).$
4) Now prove the relation:
$\sum _{k=0}^{m}\left(\genfrac{}{}{0}{}{n-k}{m-k}\right)=\left(\genfrac{}{}{0}{}{n+1}{m}\right).$
Step 2
4a) You can prove this relation in various ways. One of them is to write $\left(\genfrac{}{}{0}{}{n-m}{0}\right)$ as $\left(\genfrac{}{}{0}{}{n-m+1}{0}\right)$ and then repeatedly use the relation $\left(\genfrac{}{}{0}{}{x}{r}\right)+\left(\genfrac{}{}{0}{}{x}{r-1}\right)=\left(\genfrac{}{}{0}{}{x+1}{r}\right)$. Another method is induction.

Still Have Questions?

mafalexpicsak

Expert

Step 1

Step 2

Free Math Solver