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

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

Roger Stafford

.

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. ... Thank you Roger. ...
    (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: Best smaller matrix
    ... Roger Stafford wrote: ... >> minimum sum. ... > next selection, ... this number) of the working sum, I make it the new working set. ...
    (comp.soft-sys.matlab)
  • Re: Best smaller matrix
    ... Roger Stafford wrote: ... Then it can be shown that the sum you wish ... > Hello Murphy and Per, ... the subject of eigenvalues came up. ...
    (comp.soft-sys.matlab)
  • Re: n-column integer matrix with maximum row sum: how to?
    ... Roger Stafford wrote: ... The sum of each row must not exceed x. ... each integer in the selection produces a count of ... There are altogether m non-selected integers, ...
    (comp.soft-sys.matlab)
Loading