I'm interested in evaluating the following summation, where the value of $n$ is known:
$$\sum_{i = 0}^{2n} \sum_{j = \max(0, i – n)}^{\min(i, n)} {i \choose j}.$$
In case you're wondering where the summation comes from, it is the answer to the following question: "How many binary strings of length $\leq 2n$ can you form with no more than $n$ ones and $n$ zeros?". The summation in $i$ fixes the length of the string, and the summation in $j$ fixes the number of ones we use.
By splitting the summation from $i = 0$ to $i = n$ and $i = n + 1$ to $i = 2n$, I am able to rewrite the sum as follows:
$$\sum_{i = 0}^{n}\sum_{j = 0}^{i} {i\choose j} + \sum_{i = n + 1}^{2n} \sum_{j = i – n}^{n} {i\choose j}.$$
Call the two summations $S_1$ and $S_2$ respectively. By the sum of binomial coefficients identity, I can evaluate $S_1$ as follows:
$$S_1 = \sum_{i = 0}^{n}\sum_{j = 0}^{i} {i\choose j} = \sum_{i = 0}^{n} 2^{i} = 2^{n + 1} – 1.$$
Now, I'm having trouble evaluating $S_2$. I've tried writing out the terms to find patterns. I've also tried using Hockeystick with no luck. I've also tried switching the order of summation, but this also led me nowhere.
Can someone please help me solve this problem or provide me with a hint?
When $n = 2$, the summation evaluates to $19$. When $n = 3$, the summation evaluates to $69$. When $n = 4$, my computer program gave me $251$.
I think this is OEIS A030662, which has a few closed forms, but I want to find it myself. One interesting closed form is ${2n\choose n} – 1$.
Thank you
Best Answer
As you mentioned, the formula is ${2(n+1) \choose n+1} - 1$. What we want to compute is
$$\sum_{i=0}^n \sum_{j=0}^n {i+j \choose i}$$
The proof is just to repeatedly use
$${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$$
Let's expand our answer:
\begin{align*} {2n+2 \choose n+1} &= {2n + 1 \choose n+1} + {2n+1 \choose n}\\ &= {2n + 1 \choose n+1} + {2n \choose n} + {2n \choose n-1} \\ &= {2n + 1 \choose n+1} + {2n \choose n} + {2n-1 \choose n-1} + {2n-1 \choose n-2} \\ &= {2n + 1 \choose n+1} + {2n \choose n} + \cdots + {n+1 \choose 1} + {n+1 \choose 0} \\ &= \sum_{i=1}^{n+1} {n + i \choose i} + {n+1 \choose 0} \\ &= \sum_{i=0}^{n} {n + i + 1 \choose i + 1} + 1 \end{align*}
Now let's expand each term inside the sum:
\begin{align*} {n + i + 1 \choose i + 1} &= {n + i \choose i} + {n + i \choose i + 1}\\ &= {n + i \choose i} + {n + i - 1 \choose i} + {n + i - 1 \choose i + 1}\\ &= {n + i \choose i} + {n + i - 1 \choose i} + \cdots + {i + 1 \choose i} + {i + 1 \choose i + 1}\\ &= \sum_{j=1}^n {j + i \choose i} + {i+1 \choose i+1} \\ &= \sum_{j=0}^n {j + i \choose i}, \end{align*} as required.
P.S.: I didn't check (too much work), but I think this proof can be generalized for an arbitrary number of symbols, with each symbol having its own maximum number of usages $c_i$. In particular, for $3$ symbols the result should be something like this:
$${c_1 + c_2 + c_3 + 3 \choose c_3 + 1} {c_1 + c_2 + 2 \choose c_2 + 1} - 1$$