Combinatorics proofs (very interested in the way of thinking and strategy) Every time I am facing a "Prove the following identity in a combinatoric way" I find myself struggling for hours not knowing where to start.
I know that thinking out of the box is a must in this area, but I do believe that for those of you with more experience do have some tools and/or strategies to deal this kind of problems.
Let's for example take the following :
$$ \sum_{i=1}^{n-1} \binom{n}{i}^2 = \binom{2n}{n} - 2 $$ 
It took a while but I solved this one. I am much more interested in the strategy and not the solution itself
Please share your ideas!
 A: The following might not work for more tricky cases, and there could be a better of doing it, but here is a strategy that I use:


*

*Work backwards from each side separately, using the understanding that ${{n}\choose{k}}$ means choosing $k$ (or $n-k$) items from $n$ items, addition means "or" and multiplication means "and"

*It helps to ignore boundary cases at first, and try to converge both sides lead to counting the same thing.

*Finally, consider the boundary cases, such as over-counting or under-counting.


Take the example given in the question.  Consider the RHS.  ${2n\choose n}$ is the number of ways to choose $n$ items from $2n$ items.  Ignore $-2$ for now.
Consider the LHS.  ${n\choose i}$ is the number of ways to choose $i$ items from a set of $n$ items.  ${n\choose i}^2$ is the total number of ways to choose $i$ items from one set of $n$ items, and another $i$ items from a separate set of $n$ items.  
At this point, it helps to see that choosing $2i$ items from a total of $2n$ items does not immediately converge to the RHS.  So, let's reinterpret ${n\choose i}^2$ as the total number of ways to choose $i$ items from one set of $n$ items, and another $n-i$ items from a separate set of $n$ items, giving a total of $n$ items from $2n$ items, which is the RHS.  So we are getting closer.
Now, $i$ can be 0 or 1 or .. $n$.  So we sum ${n\choose i}^2$ for $i$ from 0 to $n$ to count the total number of ways of choose $n$ items from $2n$ items. So, 
$$\sum_{i=0}^n {n\choose i}^2 = {2n\choose n}$$
Now, consider the boundary cases and compare this to the statement we are trying to prove, where $i$ starts from 1 and ends at $n-1$.  We can then rewrite as:
$$\sum_{i=1}^{n-1} {n\choose i}^2 + {n\choose 0}^2 + {n \choose n}^2 = {2n\choose n}$$
which gives 
$$\sum_{i=1}^{n-1} {n\choose i}^2 + 2 = {2n\choose n}$$
The statement then follows.
