2
$\begingroup$

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!

  • 0
    It can be anything you want, we mostly see $k$ or $n$2012-10-24

4 Answers 4

7

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}.$

  • 0
    @MargretButton: It's already accepted. I'm glad you found this answer useful :)2012-10-24
0

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$

  • 0
    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 form2012-10-24
0

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.

  • 0
    ya sorry I havn't encountered lattice paths yet in my math adventures. thanks though!2012-10-24
0

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.