Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: integer solutions for x_1+x_2+...+x_n = k
Date: Mon, 3 Nov 2008 19:42:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 32
Message-ID: <genk6a$cke$1@fred.mathworks.com>
References: <geku21$eku$1@fred.mathworks.com> <gel0b6$3li$1@fred.mathworks.com> <gelbfg$72h$1@fred.mathworks.com> <gelf99$84m$1@fred.mathworks.com> <gemb7o$hib$1@fred.mathworks.com> <geni8e$ajn$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1225741322 12942 172.30.248.37 (3 Nov 2008 19:42:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 3 Nov 2008 19:42:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:498725


"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <geni8e$ajn$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gemb7o$hib$1@fred.mathworks.com>...
> > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gelf99$84m$1@fred.mathworks.com>...
> > >   In general the total number of solutions is (k+n-1)!/k!/(n-1)! 
> 
> > Hi Roger,
> > what is your way to derive this formula ?
> > Bruno
> 
> Hi Bruno,
> 
>   Probably the easiest way is to use mathematical induction.  Let P(n) be the proposition that the number of solutions for n non-negative integers with a sum of k is equal to
> 
>  (k+n-1)!/k!/(n-1)!
> 
> for all non-negative integers k.  It is obvious that this is true for n = 1 since there is clearly only one possible solution in that case.  Suppose that it holds for n = N.  Then we try to prove it for n = N+!.  The value of the last (the N+1 st) term may be any integer value j from j = 0 to j = k.  The remaining terms must then have a sum of k-j and by our inductive hypothesis there are
> 
>  (j+N-1)!/j!/(N-1)!
> 
> solutions for that j.  The sum of all of these,
> 
>  sum, j = 0 to k, of (j+N-1)!/j!/(N-1)! ,
> 
> is identically equal to (k+N)!/k!/N! which proves P(N+1).  This establishes the proposition P(n) for all integers n.
> 
>   This last sum equality is a known identity about the sum in a Pascal triangle along a diagonal and can be easily be proved using a further mathematical induction on k.
> 

Thank you Roger. I didn't see it yesterday after a quick look. It's relatively straightforward to prove the formula after knowing it, but derive it requires some skill. Pretty.

Bruno