Sunday, June 10, 2018

combinatorics - Proof through combinatorial argument



I am attempting to solve this counting problem through combinatorial argument. The following is the equation I am given:



$$\sum_{i=1}^n (i-1)(n-i) = \binom{n}{3}$$




I understand that the right-hand side of this equation represents a set of $n$-elements out of which we choose 3. For example I believe we can say suppose we have a group of $n$ people and we want to choose 3 out of $n$ to be in a committee. However I'm not sure how to express the left-hand side in words. If forming a committee is an appropriate way to tackle this problem then I know the left-hand side must utilize the addition and multiplication principles, but I don't know how to put it into words. Also my intuition tells me that in solving this we should first flip $$(n-i)(i-1)$$



Thanks!


Answer



Hint: split on the fact that the middle member (in sorted numerical order, the members are numbered $1$ to $n$) is $i$. Then we pick one from before and one from after.


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