# Number of solutions of $x_1 + x_2 + … + x_g \le n$

I'm trying to prove that the number of solutions of

$$x_1 + x_2 + ... + x_g \le n$$

is

$$\dbinom{g + n}{n}$$

so far I've been able to show that the number of solutions of

$$x_1 + x_2 + ... + x_g = n$$

is

$$\dbinom{g + n - 1}{n}$$

But I can't manage to see how to get from my result to the goal result. I used a partitioning argument for my result. Is this the wrong way of going about it?

Thanks!

-
I'm so not use to seeing $g$ has a subscript like that that it puzzled me for a sec ;) – Jean-Sébastien Oct 24 '12 at 2:10
Ya. It's the go-to for working with Waring's right? Is this what you're referring to? This is just the notation used in the question. – Margret Button Oct 24 '12 at 2:11
It can be anything you want, we mostly see $k$ or $n$ – Jean-Sébastien Oct 24 '12 at 2:13

There are two ways of doing this. The first way is to add them up as Ross Millikan suggested, to get $$\binom{g-1}{0}+\binom{g}{1}+\binom{g+1}{2}+\cdots+\binom{g+n-1}{n}$$ as your answer. The second way is to see that there is a bijection between the set of solutions of $$x_1+\cdots+x_g \le n$$ and the set of solutions of $$x_1+\cdots+x_{g+1}=n.$$ Hint: If $(x_1,\dots,x_g)$ is satisfies the first inequality then $$(x_1,\dots,x_g,n-x_1-\cdots-x_g)$$ satisfies the second equation.

This in fact gives a proof of the identity $$\sum_{k=0}^n \binom{g+k-1}{k} = \binom{g+n}{n}.$$

-
@Marret Button: The binomial sum "zips up" if you say ${g-1 \choose 0}+{g \choose 1}={g \choose 0}+{g \choose 1}={g+1 \choose 1},$ then combine that with the next term, and so on. – Ross Millikan Oct 24 '12 at 2:47
I really like that bijection! Great idea! @RossMillikan Thanks for your response. I was originally looking for some neat trick like this to simplify the sum. That being said, I'm having trouble seeing how that identity actually is true. – Margret Button Oct 24 '12 at 2:58
@MargretButton: You can try proving the identity by induction + Pascal's identity. – wj32 Oct 24 '12 at 3:07
@wj32 I keep trying to accept the answer, but it won't save? – Margret Button Oct 24 '12 at 4:26
@MargretButton: It's already accepted. I'm glad you found this answer useful :) – wj32 Oct 24 '12 at 4:51

You are making good progress. Hint: if the sum of the $x$'s is $\le n$, it must be one of $1, 2, 3, \ldots n-1$

-
Thank you for your response! Ya I've tried taking the sum of my result for n = 1,2,3,..,n using the factorial representation of the binomial coefficient, but I just end up with a huge mess of products that I can't force into the desired form – Margret Button Oct 24 '12 at 2:05

One way that you can approach this problem is thinking about another related problem. Can you perhaps form a nice bijection with something? Do you know anything about lattice paths? Perhaps you can think of someway to relate "filling" the lattice path with your problem.

-
ya sorry I havn't encountered lattice paths yet in my math adventures. thanks though! – Margret Button Oct 24 '12 at 2:51

You are in fact very close. If you sum over all the solutions from $x_1 + \cdots + x_g = 0,\ 1,\ \cdots n$ then you end up with $$\sum_{i=0}^n\binom{g+i-1}{i} = \sum_{i=0}^n\binom{g+i-1}{g-1}$$ There is a rather well known binomial sum identity that states $$\sum_{i = k}^n\binom{i}{k} = \binom{n+1}{k+1}$$ You might want to prove this identity first and then apply it to our sum.

-