Count the solutions in nonnegative integers

[Jamin2112]

Homework Statement

Count the solutions in nonnegative integers x₁,...,x_k to x₁ + ... + x_k=n

Homework Equations

There's a Theorem in the chapter (shows that the answer is "n+k-1 choose k-1" but we're not allowed to use it.

The Attempt at a Solution

Well, obviously you can just have x₁ and make equal to n, or you can make x₁,...,x_k=n all equal to one, or do a bunch of stuff in between.

No stunning revelations for me, though. Ideas for how to construct a formula?

 

[Raskolnikov]

[STRIKE]Firstly, I'm assuming it's supposed to be positive integers only? Because if it's all "nonnegative integers" as you said, then we would have infinitely many solutions. 0 is a nonnegative integer. That would allow you to have as many x_i = 0 as you wanted.[/STRIKE]

You can prove it by induction. Prove your formula {{n + k - 1} \choose {k - 1}} works for n = 0.

Assume your formula holds true for all cases with n \leq r. Consider the case where n = r + 1. If x_1 = 1, then the remaining x's must add to r, for which we already have the formula. Similarly, if x_1 = 2, 3, ... , r + 1, then the remaining x's must add to r - 1, r - 2, ... , 1, 0, to all of which we have the formula for by our induction hypothesis. So it comes down to proving

\sum_{i = 0}^{r + 1} {{i + k - 1} \choose {k - 1}} = {{(r + 1) + (k - 1)} \choose {(k - 1) + 1}} = {{r + k} \choose {k}}.

 

[Raskolnikov]

Oh and to prove that, the following theorem (also proved easily by induction) might be useful:

<br /> {n \choose k} + {n \choose {k + 1}} = {{n + 1} \choose {k + 1}}. <br />

 

[Petek]

@Raskolnikov,

I was getting ready to post some hints, which were going to be very similar to what you wrote. However, I interpreted the problem to allow some of the x_i = 0, but k is fixed. (In other words, to allow the solutions to be nonnegative.) If so, then the possibility of having an unlimited number of zeros is eliminated. If you are allowing k to vary, then how would you handle, for example, the case n = 3? Would you not have to consider the three equations

x_1 = 3
x_1 + x_2 = 3 and
x_1 + x_2 + x_3 = 3?

If we assume that k is fixed, then your argument works fine (except for a typo in your first binomial coefficient: you meant k - 1 instead of k + 1).

Do you agree?

Petek

 

[Raskolnikov]

@Petek,

Thanks for pointing out my typo. That's the problem with copy-pasting haha. It's fixed now.

And yes, I agree. My method wouldn't quite work if we allowed k to vary. In retrospect, I should have realized that something was off in my process seeing as how the sum we need to prove goes from i = 0 to i = r + 1, i.e., we have r + 2 terms for the case where n = r + 1...so x = 0 needs to be included.

Thanks for fixing the error in my thinking. Do you have any thoughts on what we would do if we were to allow k to vary?

 

[Petek]

@Petek,

Thanks for pointing out my typo. That's the problem with copy-pasting haha. It's fixed now.

And yes, I agree. My method wouldn't quite work if we allowed k to vary. In retrospect, I should have realized that something was off in my process seeing as how the sum we need to prove goes from i = 0 to i = r + 1, i.e., we have r + 2 terms for the case where n = r + 1...so x = 0 needs to be included.

Thanks for fixing the error in my thinking. Do you have any thoughts on what we would do if we were to allow k to vary?

I suggest that we allow the OP to comment on the advice that's been provided. Afterward we can discuss other possibilities.

Petek

 

[Petek]

@Jamin2112,

I found another way to solve your problem, possibly easier than the above solution. Here's a hint:

Show that the solution to your problem is the same as the number of ways to place n indistinguishable balls into k distinguishable urns. Then show that this number is the same as the answer to your problem. Here, "indistinguishable" means that the balls all look alike and "distinguishable" means that the urns may be thought as being labeled. So, for example, placing two balls into urn #1 and one ball into urn #2 is different than placing one ball into urn #1 and two balls into urn #2.

This approach makes it more clear that the original problem involves combinatorics.

 

[ross_tang]

In this article in http://www.voofie.com/concept/Mathematics/" :

http://www.voofie.com/content/133/repeated-sum-and-partial-difference-equation/"

I first gave a standard method in solving the problem (probably the same approach as your theorem). Then I solve it using a totally difference approach by transforming it into a partial difference equation. Finally, I derived 1 more result for repeated sum, namely:

\sum _{n_1=0}^n \sum _{n_2=0}^{n_1} \sum _{n_3=0}^{n_2} \text{...}\sum _{n_{k}=0}^{n_{k-1}}a_{n_{k}} = \sum _{j=0}^n \binom{n+k-j-1}{n-j}a_j