4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Did I understand the problem correctly? "Find the number of binary strings with at most $n$ ones and at most $n$ zeroes" $\endgroup$
    – Dmitry
    Jul 19, 2020 at 0:06
  • $\begingroup$ Yes, that is correct @Dmitry. If you can solve that problem without evaluating the summation, I will also be happy with your answer. I guess that would have been a better name for the problem. $\endgroup$
    – user790132
    Jul 19, 2020 at 0:07

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.