3 Attachment(s)

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:

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

1 Attachment(s)

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.