United States — Team Selection Test

Solution (By Josh Nichols-Barrer). Observe that the right-hand side of the given expression is the $(n+1)^{\text{th}}$ Catalan number, which we recall is the number of well-formed strings of $(n+1)$ pairs of parentheses. Given such a string, let its signature $k$ be the integer represented in binary by the $n$-term string whose $r^{\text{th}}$ digit from the left is 0 or 1 according to whether the $(2r+1)^{\text{th}}$ parenthesis from the left is closed or open, respectively.
Let $d_k$ be the number of well-formed strings of $(n+1)$ pairs of parentheses with signature $k$. Notice that the value of $d_k$ does not depend on $n$, as adding leading 0's to the binary representation of $k$ inserts strings of the form $(\,)$ after the leading open parenthesis. It suffices to show that $c_k$ and $d_k$ coincide.
Note that $d_0 = c_0 = 1$ for any $n$, as a string of parentheses with signature 0 must take the form
$$((() \cdots ())).$$
It remains only to show that $d_k$ and $c_k$ satisfy the same recursion. First, if a string has signature $2k+1$, its signature has a trailing 1, which forces the parenthesis string to end with $(\,)$. Thus, the number of strings of $(n+1)$ pairs of parentheses with signature $2k+1$ simply equals the number of strings of $n$ pairs of parentheses with signature $k$, which shows that $d_{2k+1} = d_k$ (since $d_k$ was independent of $n$).
Now consider a string of $n+1$ pairs of parentheses with signature $2k$, where $2^e$ is the largest power of 2 dividing $k$. In this case, $k$ has exactly $e$ trailing 0's. Consider the open parenthesis at position $2n-2e-1$. If the parenthesis to its immediate right is a closed parenthesis, then these two may be removed as a pair, leaving a string with signature $k-2^e$. If the parenthesis at position $2n-2e$ is open, then it may be removed with the parenthesis to its right (a closed parenthesis because $2k$ had $e+1$ trailing 0's), leaving a string with signature $k$. Both operations are reversible, showing that $d_{2k} = d_k + d_{k-2^e}$.
Therefore, $d_k$ and $c_k$ have the same initial value and are uniquely determined by the same recursion, so $d_k = c_k$ for all $k \ge 0$, as needed.