Re: integer solutions for x_1+x_2+...+x_n = k

"Roger Stafford" <ellieandrogerxyzzy@xxxxxxxxxxxxxxxxxxxxxx> wrote in message <geni8e$ajn$1@xxxxxxxxxxxxxxxxxx>...
"Bruno Luong" <b.luong@xxxxxxxxxxxxxxxxxxxx> wrote in message <gemb7o$hib$1@xxxxxxxxxxxxxxxxxx>...
"Roger Stafford" <ellieandrogerxyzzy@xxxxxxxxxxxxxxxxxxxxxx> wrote in message <gelf99$84m$1@xxxxxxxxxxxxxxxxxx>...
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

.

Relevant Pages

  • Re: integer solutions for x_1+x_2+...+x_n = k
    ... Let Pbe the proposition that the number of solutions for n non-negative integers with a sum of k is equal to ... 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. ... Roger Stafford ...
    (comp.soft-sys.matlab)
  • Re: (Discrete Math - Induction) Formula Differentiation
    ... ANY hints on how the derivative of the sum of terms of a G.P will get ... problem is from the Mathematical Induction chapter of my Discrete ...
    (sci.math)
  • Re: Cumulative Sums in Pivot Tables
    ... Roger - I did play with it, but even when I select running total, it will sum ... > see the subtotals beneath the row of actuals, ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Help save a life - offset, Index/Match or something else?
    ... Thanks for the reply Roger. ... What I really need is to be able to sum multiple values. ... sheet that the two columns on my YTD tab would shift to show Jan 06-May 06 ... If someone could at least help me with how to do the YTD tab I would ...
    (microsoft.public.excel.misc)
  • Re: Formula Question for Excel 2007
    ... Thanks Roger for the wonderful suggestion. ... "Roger Govier" wrote: ... I'm using Excel 2007 to keep track of attendance for classes held on ... Sum up all the data for each time you see ...
    (microsoft.public.excel.misc)
Loading