Here is a combinatorial proof that
$$
\binom{2n}{n} - C_n = \sum_{k=1}^n \frac12\binom{2k}{k} C_{n-k}.
$$
Since $C_n = \frac{1}{n+1}\binom{2n}{n}$, the left-hand side simplifies to $n C_n$, and after multiplying by $2$, this gives us the equation you want.
Both sides of the equation above are going to count walks of length $2n$ that start and end at $0$, but do dip below the $x$-axis. Since $\binom{2n}{n}$ counts the total number of walks that start and end at $0$, and $C_n$ counts the number that don't dip below the $x$-axis, the number we are counting is $\binom{2n}{n} - C_n$.
Now split these walks up into $n$ classes based on the last step at which the walk goes from $-1$ to $0$. Such a step must exist, because once we dip below the $x$-axis, we have to come back up to $0$ at some point.
The number of walks in which this step is the $(2k)^{\text{th}}$ step is exactly $\frac12 \binom{2k}{k} C_{n-k}$:
- Out of the $\binom{2k}{k}$ walks that return to $0$ on the $(2k)^{\text{th}}$ step, exactly half go from $-1$ to $0$ on that step. (The other half go from $1$ to $0$.)
- In the remainder of the walk, we can never dip below $0$, since that step was the last time we came back from below the $x$-axis, so there are $C_{n-k}$ ways to complete the walk.
Summing over all values of $k$, we get the right-hand side of the equation above.
The number of ways to fully parenthesize a string of $n$ letters, $C_{n-1}$, obeys the following recurrence:
$$
C_{n-1} = \sum_{i=1}^{n-1}C_{i-1}C_{n-i-1}
$$
To see this, consider the two "shallowest" groups in the parenthesization. Namely, ignoring the leftmost ( and the rightmost ), look at the parenthesis matching the leftmost (. This will surround the first $i$ letters in the string, which can be further paranthesized in $C_{i-1}$ ways, while the latter $n-i$ letters can be parenthesized in $C_{n-i-1}$ ways. For example when $n=5$, the $*$ illustrates all of the break points:
(1 * (2 (3 (4 5)))) C(0) * C(4) strings where the break point
(1 * (2 ((3 4) 5))) is after i=1
(1 * ((2 3) (4 5)))
(1 * ((2 (3 4)) 5))
(1 * (((2 3) 4) 5))
((1 2) * (3 (4 5))) C(1) * C(2) strings where the break point
((1 2) * ((3 4) 5)) is after i=2
((1 (2 3)) * (4 5)) C(2) * C(1) strings where the break point
(((1 2) 3) * (4 5)) is after i=3
((1 (2 (3 4))) * 5) C(4) * C(0) strings where the break point
((1 ((2 3) 4)) * 5) is after i=4
(((1 2) (3 4)) * 5)
(((1 (2 3)) 4) * 5)
((((1 2) 3) 4) * 5)
This recurrence gives you a quickly computable bijection from the first $C_{n-1}$ non-negative integers to binary trees. You are given an integer $k$ for which $0\le k\le C_{n-1}-1$. Compute the partial sums
$$
\sum_{i=1}^{s-1} C_{i-1}C_{n-i-1}
$$
to find the largest number $s\ge 1$ for which that partial sum is at most $k$. Then, insert parentheses into the list of numbers (1 2 3 ... n) as follows:
((1 2 ... s) (s+1 s+2 ... n))
If $s=1$, you can omit the parentheses around (1), and similarly when $s=n-1$ around (n).
Then, letting $$e=k - \Big(\sum_{i=1}^{s-1}C_{i-1}C_{n-i-1}\Big),$$ and letting \begin{align}k_1&=e\pmod {C_{s-1}}\\k_2&=\lfloor e/C_{s-1}\rfloor,\end{align} you will have $0\le k_1\le C_{s-1}-1$ and $0\le k_2\le C_{n-s-1}-1$, and you can recursively apply the bijections for $k_1$ to the list (1 2 ... s) and for $k_2$ to the list (s+1 s+2 ... n).
Edit: There was a "bug" in my bijection which I just fixed. You can test that it works here.
Edit2: I just fixed another off-by-one error.
Best Answer
My answer uses the same methods as that of tc2718's answer to a very similar problem.
Let $a_n$ be the quantity in question, and let $F(x)=\sum_{n\ge 0}a_nx^n$. We will evaluate $F$ by switching the order of summation, applying the binomial theorem to the inner sum, rearranging a bit, and then recognizing the expression as the Catalan generating function evaluated at $-x-x^2$. $$ \begin{align} F(x) &=\sum_{n\ge 0}\sum_{k=0}^n (-1)^k C_k \binom{k+2}{n-k}x^n \\&=\sum_{k=0}^\infty (-1)^k C_k \sum_{n= k}^\infty\binom{k+2}{n-k}x^n \\&=\sum_{k=0}^\infty (-1)^k C_k \; x^k(1+x)^{k+2} \\&=(1+x)^2\sum_{k=0}^\infty C_k \; (-x-x^2)^k \\&=(1+x)^2 \frac{1-\sqrt{1-4(-x-x^2)}}{2(-x-x^2)} \\&=(1+x)^2 \frac{1-\sqrt{(1+2x)^2}}{2(-x-x^2)} \end{align} $$ Here, we must choose the branch of $\;\sqrt{\cdot}\;$ where $\sqrt{(1+2x)^2}=+(1+2x)$, since the other choice causes a pole at $x=0$, and our definition of $F(x)$ makes it clear there is no pole there. Finally, \begin{align} F(x)=(1+x)^2 \cdot \frac{1-(1+2x)}{-2x(1+x)}=1+x \end{align}
This closed form expression for $F(x)=\sum_{n\ge 0}a_nx^n$ shows that $a_0=a_1=1$, while $a_n=0$ for $n\ge 2$.