0
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

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}. $$

$\endgroup$
1
  • $\begingroup$ Was toying with the double sum method but didn't make the necessary connections. Thanks for your input. $\endgroup$
    – Black
    Commented Apr 4, 2015 at 11:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .