I am trying to determine whether $\sum_{k=m}^n {k \choose m} = {n+1 \choose m+1}$, so far I am assuming that this is a false statement, but was wondering if there was a proof indicating this is a true statement.
5
-
$\begingroup$ Sorry, let me rephrase that statement. I am assuming it is false, because I have not determined a way to prove that they are equal yet. $\endgroup$– user273581Sep 24, 2015 at 16:53
-
2$\begingroup$ The only way to conclude it is false is to find values $n,m$ where it is not true. $\endgroup$– Thomas AndrewsSep 24, 2015 at 16:53
-
1$\begingroup$ Try induction on $n$, fixed $m$. $\endgroup$– Thomas AndrewsSep 24, 2015 at 16:54
-
$\begingroup$ You might gain some insight into this problem if you identify both the right hand side and the terms being summed on the left hand side in Pascal's triangle, and proceed recursively. $\endgroup$– Brian TungSep 24, 2015 at 16:54
-
$\begingroup$ You can try to prove this by arguing in terms of counting subsets. Suppose you want to choose a subset of size $m+1$ out of numbers between $1$ and $n+1$. What if you break into cases according to what the largest number $K$ is in the subset? These cases are disjoint and cover all the possibilities for choosing your original subset. $\endgroup$– user2566092Sep 24, 2015 at 17:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
After gaining the intuition via Pascal's Triangle, the best way for a formal proof (apart from a combinatorial argument which is nice but hard to find) seems to be induction.
For $n=m$ this is clearly true. Assume it is true for some $n$. Then we want to prove it for $n+1$. That is, we need to prove that $$\sum_{k=m}^{n+1} \binom{k}{m}=\binom{n+2}{m+1}$$ But by the induction hypothesis, we have $$LHS=\sum_{k=m}^n \binom{k}{m}+\binom{n+1}{m}=\binom{n+1}{m+1}+\binom{n+1}{m}$$ So, we are left to prove $$\binom{n+1}{m+1}+\binom{n+1}{m}=\binom{n+2}{m+1}$$ This is a famous property of the binomial coefficients (which is also the elementary recursive property of Pascal's Triangle).
There are various proofs for it. Either one can use a combinatorial argument or the definition of binomial coefficients involving factorials.
Can you find a proof for this on your own?
