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