I am trying to figure out the number of solutions to the equation:
$$x_1+x_2+…+x_r\leq n$$
where $x_i$, $i=1,2,…,r$ is non-negative and $n$ is some positive given integer.
I have already solved this for the case of an equality: this is just ${n+r-1\choose r-1}$ (following the traditional "stars and bars" method).
To solve for the number of solutions to the inequality, therefore, I thought that I could just solve for each case, i.e. when $x_1+x_2+…+x_r=n-1$, then $n-2$, etc. all the way down to $\sum x_i=1$. This would make my life easy, if it's true, as all I would have to do is just sum the combination term above with the varying values of $n$. However, given some scratchwork that I've done, I'm not so sure that this is the case.
Any suggestions as to why this might be true/false would be sincerely appreciated. If it is wrong, I just cannot find where the flaw in my thinking is.
Best Answer
Just by taking the sum we get $$\sum_{k=0}^n{k+r-1\choose r-1}={n+r\choose r}$$ where we used the Hockey-stick identity. The same result can be obtained by enumerating the number of non-negative solutions of the equation $$x_1+x_2+...+x_r+y= n.$$ where $y$ is a non-negative integer dummy variable.