# Thread: Koshy-Elementary Number Theory with Applications...Induction, sums and binomial.

1. ## 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 $\displaystyle$\tbinom{n}{r}=\frac{n}{r}\tbinom{n-1}{r-1}.

That is easy, I did this:

Then the next one was:
Show that:

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

2. ## Re: Koshy-Elementary Number Theory with Applications...Induction, sums and binomial.

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