# Upper bound to multinomial coefficient sum

I'm currently stuck on what seems like a very trivial problem. I have the following calculation $$\sum_{k_1+k_2=0}^{n} {n \choose n - k_1 - k_2, k_1, k_2}^2 \le \sum_{k_1+k_2=0}^{n} {n \choose \frac{n}{3}, \frac{n}{3}, \frac{n}{3}}^2 = {n \choose \frac{n}{3}, \frac{n}{3}, \frac{n}{3}}^2 \sum_{k_1+k_2=0}^{n} 1$$

I need to find the value of the following to complete the calculation $$\sum_{k_1+k_2=0}^{n} 1$$

At first glance, I thought that it would equal to $(n + 1)$ but now I'm fairly sure it won't be. This seems like a combinatorial problem where we have to find all $k_1$ and $k_2$ such that the sum of the two will be every integer from $0$ to $n$.

Any help would be appreciated with finding the value of this sum.

• Can't you rephrase this as the standard sum $1 + 2 + \ldots + n + (n+1)$? Commented Apr 4, 2015 at 11:22
• My initial thought was that this would just be a series of $1$'s from 0 to n. Is that what you meant? Commented Apr 4, 2015 at 11:28
• I agree with your second take, ennumerate the pairs $(k_1, k_2)$ such that $0 \le k_1+k_2 \le n$. Commented Apr 4, 2015 at 11:31
• Also, note that you have $0\leq k_1,k_2\leq n$. Commented Apr 4, 2015 at 11:38

It looks to me as if this is a double sum with $0\le k_1 \le n$, $0\le k_2 \le n$ and $0\le k_1+k_2 \le n$.
You could rewrite it as a double sum with $0\le k_1 \le n$ and $0\le k_2 \le n-k_1$, i.e. as $$\sum_{k_1=0}^{n} \sum_{k_2=0}^{n-k_1} 1 = \sum_{k_1=0}^{n} (n-k_1+1) = n(n+1)- \left(\sum_{k_1=0}^{n} k_1\right) +(n+1) = \frac{(n+1)(n+2)}{2}.$$