I am attempting to show that:

$$ \sum\limits_{q=0}^Q\binom{q + d - 1}{d - 1} = (Q + 1)d^Q $$

But I am totally lost. I was hoping I could use something as simple as the binomial theorem, but I quickly get stuck. Any help is greatly appreciated...

EDIT: Thanks to @stochasticboy321 for your answer! I see now that the equality cant hold... Im now trying to prove by induction a weaker, but as useful claim for my purpose, that: $$ \sum\limits_{q=0}^Q\binom{q + d - 1}{d - 1} \leq (Q + 1)d^Q $$ for $d > 0$ and $Q > 0$. But Ive gotten stuck once more :D.

Base case, $Q = 1$: $$ \binom{d - 1}{d - 1} + \binom{1 + d - 1}{d - 1} \leq 2d \implies 1 + d \leq 2d $$

Assume $\sum_{q=0}^k\binom{q + d - 1}{d - 1} \leq (k + 1)d^k$, prove:

$$ \sum\limits_{q=0}^{k+1}\binom{q + d - 1}{d - 1} \leq (k + 2)d^{k + 1} \\ \implies \sum\limits_{q=0}^k\binom{q + d - 1}{d - 1} + \binom{k + d}{d - 1} \leq (k + 2)d^{k + 1} \\ \implies (k + 1)d^k + \binom{k + d}{d - 1} \leq (k + 2)d^{k+1} $$ My strategy so far has been trying to expand $\binom{k + d}{d - 1}$ to its factorial form and reduce, but I really dont know what Im doing...

  • $\begingroup$ This is not correct. Consider $d=2$. Then $LHS = \sum_0^Q q+1 = \frac{1}{2}(Q+1)(Q+2) \neq (Q+1)2^Q = RHS$. Indeed, wolfram alpha gives the closed form $\frac{(Q+1)}{d}\binom{d+Q}{d-1}$. $\endgroup$ – stochasticboy321 Jan 23 '17 at 0:11

As noted in the comments, the identity asked is incorrect, and the correct identity is $$\sum\limits_{q=0}^Q\binom{q + d - 1}{d - 1} = \frac{Q+1}{d} \binom{Q+d}{d-1} = \binom{Q+d}{d}.$$ The following is a combinatorial proof of the same. Note that, by stars and bars, $\binom{q+d-1}{d-1}$ is the number of non-negative integer solutions to the equation $x_1+x_2+ \dots + x_d = q$. Thus, the summation is the number of non-negative integer solutions to $x_1+x_2+\dots + x_d \le Q$. But each non-negative integer solution of $x_1+x_2+\dots + x_d \le Q$ can be identified with a non-negative integer solution of $x_1+x_2+\dots + x_d +s = Q$, and the latter has $\binom{Q+d}{d}$ solutions. QED.

Regarding you edit - it's much easier to go inductively in $d$.

Claim: For $Q,d \ge 1, \binom{Q+d}{d} \le (Q+1)d^Q.$

Pf. Note that for every $Q$, $\binom{Q+0}{0} = Q \le Q+1,$ and thus the result holds for $d = 1$. We assume the result for $(Q,d)$. Now, for $Q,d \ge 1$,\begin{align*} (d+1)^{Q+1} \overset{(a)}\ge& d^{Q+1} + (Q+1)d^Q = d^Q(Q+d+1)\\ \iff (Q+1)(d+1)^Q \ge& \frac{(Q+1)d^Q (Q+d+1)}{d+1} \\ \overset{(b)}\implies (Q+1)(d+1)^Q \ge& \binom{Q+d}{d} \frac{Q+d+1}{d+1} = \binom{Q+d+1}{d+1} \end{align*}

where inequality $(a)$ is because each term in the binomial theorem expansion of $(d+1)^{Q+1}$ is positive, and implication $(b)$ is due to the induction hypothesis. QED.

| cite | improve this answer | |

Algebraic Proof
Using formulas from GouldBk.pdf http://www.dsi.dsi.unifi.it/~resp/GouldBK.pdf
Partial sum ((P) in GouldBk.pdf page 14)
${\displaystyle \sum_{k=0}^{n}f_{k}=\left[t^{n}\right]\frac{f(t)}{1-t}}$
Let's rewrite the sum as
${\displaystyle \sum_{q=0}^{Q}\left(\begin{array}{c} q+d-1\\ q \end{array}\right)}$
and apply (1.49 on page 49)
${\displaystyle =\left(\begin{array}{c} d+Q\\ Q \end{array}\right)}$
Which matches the previous solution.
I couldn't do better than the 1.49 proof, which uses (BC4)
Proof (directly lifted):
${\displaystyle \sum_{q=0}^{Q}\left(\begin{array}{c} d-1+q\\ q \end{array}\right)=\left[t^{Q}\right]\frac{1}{\left(1-t\right)^{\left(d-1+1\right)}\left(1-t\right)}}=\left[t^{Q}\right]\frac{1}{\left(1-t\right)^{\left(d+1\right)}}=\left(\begin{array}{c} d+Q\\ Q \end{array}\right)$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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