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!
 A: 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}.$$
A: 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$
A: 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.
A: 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.
