A basic combinatorial sum I am interested in the following, which I think is basic which 
I don't know how to find an upper bound for:
$$
\sum_{j=1}^{d-1} \ \sum_{1 \leq i_1 \leq i_2 \leq ... \leq i_j \leq K} 1.
$$
I would appreciate any upper bounds. Thank you!
 A: The inner sum, $\sum_{1\leq i_1\leq\cdots\leq i_j\leq K}1$ is the same as the following:
Consider the following collection of differences:
$$
K-i_j\qquad i_j-i_{j-1}\quad \cdots \quad i_2-i_1\qquad i_1-1.
$$
This is a set of $j+1$ nonnegative integers whose sum is $K-1$.
Consider a set of $(K-1)+(j+1)=K+j$ objects in order (in a row).  Between these objects, there are $K+j-1$ spots.  Choose $j$ of these spots, this divides the objects into $j+1$ sets (in order).  
Let $a_s$ be the number of elements in the $s$-th set.  Then
$$
\sum_{i=1}^{j+1}a_s=K+j.
$$
Now, let $b_s=a_s-1$, then
$$
\sum_{i=1}^{j+1}b_s=K-1.
$$
Therefore, if we set $$K-i_j=b_{j+1}\qquad i_s-i_{s-1}=b_s\qquad i_1-1=b_1,$$
then we can see that 
$$\sum_{1\leq i_1\leq\cdots\leq i_j\leq K}1=\begin{pmatrix}K+j-1\\j\end{pmatrix}$$
Then, you may notice that your sum shows up in Binomial Theorem (at least the infinite version).
A: This sum is certainly not larger than 
$$
(d-1)K^{d-1},
$$
since that is the value of the summation
$$
(d-1) \sum_{i_1,i_2,\cdots,i_{d-1}=1}^K 1,
$$
which is certainly greater then sum you proposed. We can however do much better (along the lines of the comment of Micheal Burr): 
The indices $i_1\leq i_2\leq \cdots \leq i_j$ can take all the values between $1$ and $K$ and are allowed to have coinciding values. This means that the indices form a subset (with repetition) of the set $\{1,\cdots, K\}$. The ordering of the indices makes sure that every subset occurs exactly once. 
The number of subsets of this form is
$$
\frac{(K+j-1)!}{j!(K-1)!}.
$$
So your sum is given by 
$$
\sum_{j=1}^{d-1}\frac{(K+j-1)!}{j!(K-1)!}=\frac{( d (d-1 + K)!) -d! K!}{(K d! (K-1)!)},
$$
where I computed the sum exactly using Mathematica.
