Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

4 Answers 4

up vote 7 down vote accepted

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

share|improve this answer
1  
@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
add comment

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$

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
ya sorry I havn't encountered lattice paths yet in my math adventures. thanks though! –  Margret Button Oct 24 '12 at 2:51
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.