You didn't say you must have a proof by induction (I don't see an easy inductive proof). Here's an easy proof:
The formula represents two different way of counting the ways one can choose n people from 2n people with exactly n men and n women -- a term of the sum represents choosing r men and thus n-r women; letting r vary from 0 to n we get the total number of ways of choosing the n people. This is in fact the way I remember the formula.
D. E. Knuth's Art of Computer Programming, Vol I has a wealth of combinatoric formulas like this. Perhaps even more can be found in Concrete Mathematics by Knuth, et al.