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
    I'm so not use to seeing $g$ has a subscript like that that it puzzled me for a sec ;)2012-10-24
  • 0
    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.2012-10-24
  • 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}.$$

  • 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.2012-10-24
  • 0
    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.2012-10-24
  • 0
    @MargretButton: You can try proving the identity by induction + Pascal's identity.2012-10-24
  • 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.