Proving upper bound, sum over a product of binomial coefficients I'd like to proof the following inequality for $d,D \in \mathbb{N}$:
$$
\sum_{k=0}^{D} \binom{D}{k}\binom{d+D-k-1}{D-1} \leq 2D d^{D-1}.
$$
In case $B>A$ we define $\binom{A}{B}:=0$.
This upper bound is exact in the case $D=1,2$. I'm not quite sure how tackle this problem in a somewhat elegant way. 
 A: The proof has two parts: 


*

*We give a combinatorial interpretation of the left hand side; by double counting, this will yield an equivalent sum;

*Term-by-term inequality will give the desired result.


Let's interpret the left hand side.
Let $S$ be a set of $D$ elements, and $T$ a set of $d-1$ elements.
The LHS counts the number of ways of choosing $A \subset S, B \subset S \cup T$ disjoint, with $|B| = D-1$. In your sum, $k$ denote the number of elements of $A$: the first binomial counts the number of ways of choosing $A$, and the other binomial counts the number of ways of choosing $B$ from the remaining $(D-k)+(d-1)$ elements.
This is equivalent to counting subsets $X \subset S, Y \subset S, Z \subset T$ disjoint such that $|Y| +|Z| = D-1$: $A$ becomes $X$, and $B$ becomes $(B \cap S) \cup (B \cap T) = Y \cup Z$. We count these triples by firstly choosing $Y$, then $Z$, then $X$. In this way we get ($j$ is the cardinality of $Y$):
$$ LHS = \sum_{j=0}^{D-1} \binom{D}{j} \binom{d-1}{D-1-j} 2^{D-j} $$
Can you see that? $Y$ is a subset of $S$ of $j$ elements, $Z$ is a subset of $T$ of the left-to-choose $D-1-j$ elements, and $X$ is a subset of $S\setminus Y$. 
Here it comes the algebraic part. We will use that:


*

*$$\binom{D}{j} = \frac{D!}{(D-j)! j!} = \frac{D}{D-j} \frac{(D-1)!}{(D-j-1)! j!} = \frac{D}{D-j} \binom{D-1}{j} $$

*$ 2^n \le (n+1)!$ indeed, it is satisfied for $n=0,1$, and thereafter the rhs grows faster than the LHS.

*$$\binom{m}{k} = \frac{m (m-1) \ldots (m-k+1)}{k!} \le \frac{m^k}{k!}$$
Hence, we have
$$\sum_{j=0}^{D-1} \binom{D}{j} \binom{d-1}{D-1-j} 2^{D-j} = \sum_{j=0}^{D-1} \frac{D}{D-j}\binom{D-1}{j} \binom{d-1}{D-1-j} 2^{D-j} \le  $$
$$ D \sum_{j=0}^{D-1} \frac{1}{D-j}\binom{D-1}{j} \frac{(d-1)^{D-1-j}}{(D-1-j)!} 2^{D-j} = 2D \sum_{j=0}^{D-1} \binom{D-1}{j} \frac{(d-1)^{D-1-j}}{(D-j)!} 2^{D-1-j} \le $$
$$ 2D \sum_{j=0}^{D-1} \binom{D-1}{j}(d-1)^{D-1-j} = 2Dd^{D-1} $$
as desired.
