Koshy-Elementary Number Theory with Applications...Induction, sums and binomial.
Well, I have a problem. These are some exercises from the Koshy's book about Number Theory...
The first is:
Verify that .
That is easy, I did this:
Then the next one was:
I tried to prove it using Mathematical Induction, but I don't get to the result...
I'll show what I've done:
But I don't know how to get to where I wanna get...
Re: Koshy-Elementary Number Theory with Applications...Induction, sums and binomial.
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.