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

• Apr 2nd 2013, 06:13 PM
Leviathantheesper
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 $\tbinom{n}{r}=\frac{n}{r}\tbinom{n-1}{r-1}$.

That is easy, I did this:
Attachment 27775
Then the next one was:
Show that:
Attachment 27776

I tried to prove it using Mathematical Induction, but I don't get to the result...
I'll show what I've done:
Attachment 27777
But I don't know how to get to where I wanna get...
• Apr 4th 2013, 10:56 PM
johng
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:

Attachment 27809

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.