Re: induction problem for proving that (n+k)!/n! is divisible by k!
- From: Bill Dubuque <wgd@xxxxxxxxxxxxxxxxxxxx>
- Date: 20 Apr 2006 17:29:19 -0400
vysotin@xxxxxxxxx wrote:
Thank you all, especially Herman Rubin and Vickson. Pascals triangle
relation solves it, although one still has to make somewhat nontrivial
two-parameter induction ...
As I explained in a prior post here the induction becomes
completely trivial if you view it via the binomial theorem
i.e. via the generating function (1+x)^n = Sum C(n,k) x^k
The integrality of C(n,k) then amounts to the triviality
(1+x)^n has integer coef's implies so does (1+x)^(n+1)
because (1+x)^(n+1) = (1+x) (1+x)^n
The binomial coefficient recurrence comes from taking
the coef's of x^k in the prior displayed equation.
Notice how much simpler the recurrence (and induction)
becomes when translated into generating function terms.
--Bill Dubuque
.
- References:
- Prev by Date: Re: Line Intersections
- Next by Date: Is there a transform for computing dropout rate?
- Previous by thread: Re: induction problem for proving that (n+k)!/n! is divisible by k!
- Next by thread: Re: induction problem for proving that (n+k)!/n! is divisible by k!
- Index(es):
Relevant Pages
|
Loading
