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.
Here is a tentative proof:
We first notice that by Kummer theorem $\binom{2n}{2m} \equiv \binom{n}{m} \bmod 2$, so that it suffices to show that $$ S_q(n) \equiv T_q(n) \pmod 2$$ where
\begin{align*}
S_q(n):=&\sum_k \binom{k}{n-k}\binom{n+3q}{2k+2q+1}\\
T_q(n):=&\binom{n+3q}{2q-1}.
\end{align*}
From here, the symbol $\sim$ means has the same parity as.
We have
$\binom{a+1}{b+1}\sim \binom{a}{b+1}+\binom{a}{b}$ but also $\binom{a+2}{b+2}\sim \binom{a+2}{b}+\binom{a}{b}$.
We have
\begin{align*} T_q(n+2)&\sim \binom{n+3q+2}{2q-1} \sim \binom{n+3q}{2q-1}+\binom{n+3q}{2q-3}\\
&\sim T_q(n) +\binom{n+3+3(q-1)}{2(q-1)-1} \\
&\sim T_q(n) +T_{q-1}(n+3) \\
T_q(n+3)&\sim T_{q+1}(n+2)+ T_{q+1}(n)
\end{align*}
On the other hand, we have
\begin{align*}S_q(n+3)& \sim \sum_k \binom{k}{n+3-k}\binom{n+3q+3}{2k+2q+1}\\
&\sim \sum_k \binom{k}{n+2-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\
&\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\
&+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\
&\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3q+1}{2(k-1)+2q+3}\\
&+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\
&\sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)+1}\\
&+ \sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\
& \sim \sum_k \binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)}{2(k-1)+2(q+1)+1}\\
&+\sum_k\binom{k-1}{n+2-(k-1)}\binom{n+2+3(q+1)-2}{2(k-1)+2(q+1)-1}\\
&+\sum_k \binom{k-1}{n+1-(k-1)}\binom{n+2+3q+1}{2k+2q+1}\\
&\sim S_{q+1}(n+2) +\sum_k\binom{k}{n+2-k}\binom{n+3(q+1)}{2k+2(q+1)-1}\\
&+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
&\sim S_{q+1}(n+2) \\&+\sum_k\binom{k}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\
&+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
&\sim S_{q+1}(n+2)+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\
&+\sum_k\binom{k-1}{n-(k-1)}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}\\
&+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
&\sim S_{q+1}(n+2)+ S_{q+1}(n) \\&+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
&\sim S_{q+1}(n+2)+ S_{q+1}(n)+2\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
&\sim S_{q+1}(n+2)+ S_{q+1}(n) \\&+\sum_k\binom{k-1}{n+2-k}\binom{n+3(q+1)}{2(k-1)+2(q+1)+1}+\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
&\sim S_{q+1}(n+2)+ S_{q+1}(n)+2\sum_k \binom{k}{n+1-k}\binom{n+3(q+1)}{2k+2(q+1)+1}\\
S_q(n+3)&\sim S_{q+1}(n+2)+ S_{q+1}(n)
\end{align*}
So the parity of both $ S_q(n)$ and $ T_q(n)$ satisfy the same third order linear recurrence on $n$. Then in order to show that $ S_q(n) \sim T_q(n)$, it suffices to show that $ S_q(0) \sim T_q(0)$, $ S_q(1) \sim T_q(1)$ and $ S_q(2) \sim T_q(2)$.
$S_q(0)-T_q(0)$ is clearly an even integer since
$$S_q(0)-T_q(0)= \binom{3q}{q+1}-\binom{3q}{q-1}=2 \binom{3q+1}{q-1}.$$
We have $T_q(1)-S_q(1)= \binom{3q+1}{q+2}-\binom{3q+1}{q-2}$. After some calculation we find $$T_q(1)-S_q(1)= 2\frac{5q+7}{3q+3}\binom{3q+3}{q-1}$$ which is an even integer since \begin{align*}\binom{3q+3}{q-1}(5q+7) &\equiv \binom{3q+3}{q-1}(2q+4)\pmod {3q+3}\\
&\equiv-\binom{3q+3}{q-1}(q-1)\pmod {3q+3}\\
&\equiv-\binom{3q+2}{q-2}(3q+3)\pmod {3q+3}\\
&\equiv 0\pmod {3q+3}\end{align*}
Also, after some calculation, it can be shown that
\begin{align*}
T_q(2)-S_q(2) &= \binom{3q+2}{q+3}-\binom{3q+2}{q-1}-\binom{3q+2}{q-3}\\
&= 2 \binom{3q+5}{q-1} \frac{54+301q+258q^2+59q^3}{(3q+5)(3q+4)(3q+3)}.
\end{align*}
Then, to complete the proof, we need to show that
$$ \binom{3q+5}{q-1} (54+301q+258q^2+59q^3)\equiv 0 \pmod {(3q+5)(3q+4)(3q+3)}.$$
We have $$ (54+301q+258q^2+59q^3) \equiv (q-1)(66+47q+5q^2)\pmod {(3q+5)(3q+4)(3q+3)}.$$
Then $$ \binom{3q+5}{q-1} (54+301q+258q^2+59q^3) \equiv (3q+5)\binom{3q+4}{q-2}(66+47q+5q^2)\pmod {(3q+5)(3q+4)(3q+3)}.$$
Then it suffices to show that
$$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {(3q+4)(3q+3)}.$$
But $3q+4$ and $3q+3$ are coprime, so we need to show that
$$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {3q+4}$$
and
$$ \binom{3q+4}{q-2}(66+47q+5q^2)\equiv 0 \pmod {3q+3}.$$
That is
$$ \binom{3q+4}{q-2}(14-q^2)\equiv 0 \pmod {3q+4} \tag1$$
and
$$ \binom{3q+4}{q-2}(24-q-q^2)\equiv 0 \pmod {3q+3}.\tag2$$
(1) is equivalent to
\begin{align*} \frac{3q+4}{q-2}\binom{3q+3}{q-3}(14-q^2)&\equiv 0 \pmod {3q+4} \\
\binom{3q+3}{q-3}(14-q^2)&\equiv 0 \pmod {q-2}\\
10\binom{3q+3}{q-3}&\equiv 0 \pmod {q-2}\\
10\frac{q-2}{3q+4}\binom{3q+4}{q-2}&\equiv 0 \pmod {q-2}\\
10\binom{3q+4}{q-2}&\equiv 0 \pmod {3q+4}.\\
\end{align*}
But the last line holds true indeed, because we know from here that
\begin{align*} \binom{3q+4}{q-2}&\equiv 0 \pmod {\frac{3q+4}{\gcd(3q+4,q-2)}}\\
&\equiv 0 \pmod {\frac{3q+4}{\gcd(10,q-2)}}\end{align*}
There remains to show the validity of (2). We have
$$ \binom{3q+4}{q-2}(24-q-q^2)= (3q+3)\binom{3q+4}{q-4} \frac{3q+4}{(q-2)(q-3)}(24-q-q^2)$$
so that we need to show that
$$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {(q-2)(q-3)}. $$
That is
$$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {q-2} $$
and
$$ \binom{3q+2}{q-4}(3q+4)(24-q-q^2)\equiv 0\pmod {q-3}. $$
That is
$$ 180\binom{3q+2}{q-4}\equiv 0\pmod {q-2} $$
and
$$ 156 \binom{3q+2}{q-4}\equiv 0\pmod {q-3}. $$
That is
$$ 180\frac{(q-2)(q-3)}{(3q+4)(q-2)}\binom{3q+4}{q-2}\equiv 0\pmod {q-2} $$
and
$$ 156 \frac{q-3}{3q+3}\binom{3q+3}{q-3}\equiv 0\pmod {q-3}. $$
That is
$$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {(3q+4)(3q+3)} $$
and
$$ 156\binom{3q+3}{q-3}\equiv 0\pmod {3q+3}. $$
That is
$$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {3q+4} \tag3$$
and
$$ 180(q-3)\binom{3q+4}{q-2}\equiv 0\pmod {3q+3} \tag4$$
and
$$ 156\binom{3q+3}{q-3}\equiv 0\pmod {3q+3}. \tag5$$
For (5) it holds true because we have $156=13\cdot 12$ a multiple of $12$ and from here, we have
\begin{align*}\binom{3q+3}{q-3}&\equiv 0\pmod {\frac{3q+3}{\gcd(3q+3,q-3)}} \\
&\equiv 0\pmod {\frac{3q+3}{\gcd(12,q-3)}} \end{align*}
For (3) it holds true because we have $180=18\cdot 10$ a multiple of $10$ and from here, we have
\begin{align*}\binom{3q+4}{q-2}&\equiv 0\pmod {\frac{3q+4}{\gcd(3q+4,q-2)}} \\
&\equiv 0\pmod {\frac{3q+2}{\gcd(10,q-2)}} \end{align*}
We have seen that there exist an integer $K$, such that $\binom{3q+3}{q-3}=K\frac{3q+3}{\gcd(12,q-3)}$. Now, with the same argument from here, we have
\begin{align*}\binom{3q+3}{q-2}&\equiv 0\pmod {\frac{3q+3}{\gcd(3q+3,q-2)}} \\
&\equiv 0\pmod {\frac{3q+3}{\gcd(9,q-2)}} \end{align*}
so there exists an integer $L$ such that $\binom{3q+3}{q-2}=L\frac{3q+3}{\gcd(9,q-2)}$.
Then
\begin{align*} 180(q-3)\binom{3q+4}{q-2}&=180(q-3)\left(\binom{3q+3}{q-2}+\binom{3q+3}{q-3}\right)\\
&= (3q+3)\left( \frac{180L(q-3)}{\gcd(9,q-2)}+\frac{180K(q-3)}{\gcd(12,q-3)}\right). \end{align*}
The second factor on the right hand side is clearly an integer and this establishes the validity of (4). The proof is finished here.
Best Answer
Look at the sequence in base 3: $$ 2,12,22,102,112,222,1002,1012,1022,1102,1112,2222,10002,10012,10022,10102,10112,10222,11002,11012,11022,11102,11112,22222,100002,100012,100022,100102,100112,100222,101002,101012,101022,101102,101112 $$ Since they all have last digit $2$, let's trim that off and see if we can find a pattern:$$ 0,1,2,10,11,22,100,101,102,110,111,222,1000,1001,1002,1010,1011,1022,1100,1101,1102,1110,1111,2222,10000,10001,10002,10010,10011,10022,10100,10101,10102,10110,10111 $$ Every number with no $2$'s is here. The pattern to the $2$'s might not be obvious, but observe that any of the numbers above with a $2$ ends with a string looking like $022\dots2$ and has no other $2$'s. Equivalently, we can say that all of the above numbers either have no $2$ or else are $1$ less than a number with no $2$. Thus, we claim the following pattern (which we will prove later).
Claim: Suppose $n=2 \mod 3$. Then $(n+1)(2n-1)$ does not divide $\binom{2n}n$ if and only if at least one of $n+1$ and $n-1$ has no $2$ in its ternary (base 3) expansion.
Let $n=d_kd_{k-1}\dots d_2d_1d_0$ be the ternary expansion of $n$. We assume $d_0=2$. The claim is equivalent to saying that $(n+1)(2n-1)\nmid\binom{2n}n$ if and only if either $d_i\ne 2$ for $i\ge 1$ (in which case $n-1$ has no $2$ in ternary) or if for some $i$, the final $i$ digits of $n$ are $0222\dots2$ and none of the previous digits of $n$ are $2$ (in which case $n+1$ has no $2$ in it).
As far as density is concerned, these numbers have density $0$, since the set of numbers with no $2$ in their ternary expansion has density $0$ (c.f. the Kempner series). If $S$ is this set, then we claim the set of numbers such that $(n+1)(2n-1)\nmid\binom{2n}{n}$ is exactly $$ \left((S+1)\cup(S-1)\right) \cap (3\mathbb{N}+2) $$ Since $S$ has density $0$, so does $(S+1)\cup(S-1)$.
Proof of claim:
Let $$ K_n = \frac{3}{(2n-1)(n+1)}\binom{2n}{n} $$ which is an integer sequence, hence $(2n-1)(n+1)\nmid\binom{2n}{n}$ is equivalent to $3\nmid K_n$. We let $m=\frac{n-2}{3}$. Then, in base $3$, $$ m = d_kd_{k-1}\dots d_2d_1 $$ Then, define $$ \ell_m = \max\left\{\ell\in\mathbb{N} \text{ such that } 3^\ell \mid K_{3m+2}\right\} $$ so it suffices to find when $\ell_m=0$. We observe \begin{eqnarray} K_{n} &=& \frac{3}{(2n-1)(n+1)}\binom{2n}{n}=\frac{24(2n-5)(2n-3)(2n-1)}{(2n-1)(n+1)(n-2)(n-1)n}\binom{2(n-3)}{n-3} \\&=&\frac{8(2n-5)(2n-3)(2n-1)(2(n-3)-1)(n-2)}{(2n-1)(n+1)(n-2)(n-1)n} K_{n-3}\\ &=&8\frac{(2n-7)(2n-5)(2n-3)}{(n-1)n(n+1)} K_{n-3} \end{eqnarray} Thus we have \begin{eqnarray} K_{3m+2} &=& 8\frac{(6m-3)(6m-1)(6m+1)}{(3m+1)(3m+2)(3m+3)} \cdot K_{3(m-1)+2}\\&=&\frac{2m-1}{m+1}\cdot K_{3(m-1) +2}\cdot (\text{rational number with no power of 3 in it}) \end{eqnarray} Thus $\ell_m = \ell_{m-1}$ unless the fraction $\frac{2m-1}{m+1}$ has a power of $3$ in the numerator or denominator, which happens exactly when one of $2m-1$ or $m+1$ is a multiple of $9$. Both numerator and denominator are divisible by 3 exactly when $m$ is $2$ mod $3$. If $m$ is $2$ mod $9$, then both $2m-1$ and $m+1$ have exactly one factor $3$. If $m$ is $5$ or $8$ mod $9$, the fraction will have extra factors of $3$ in either the numerator or denominator, but not both (they cannot both be multiples of $9$. Thus we get the following recurrence for $\ell_m$:$$ \ell_m=\begin{cases}0,&m=0\\\ell_{m-1} + \max\{u : 3^{u+1} \mid (2m-1)\}, & m\equiv5\mod 9\\ \ell_{m-1} - \max\{ u:3^{u+1}\mid (m+1)\},&m\equiv 8\mod 9\\ \ell_{m-1},&\text{otherwise}\end{cases} $$ Thus, we can see that as we move through different classes mode $3^{u+1}$, we add $u$ at $\frac{3^{u+1}-1}2$ and subtract $u$ at $3^{u+1}-1$. Thus, we have that $\ell_m$ is a sum of some subset of $\{0,...,u\}$ where $3^{u+1}\le2m-1$. Each element of the set is included in the sum if and only if $m\hspace{2pt}(\text{mod } 3^{u+1})$ is in $\left[\frac{3^{u+1}-1}2,3^{u+1}-2\right]$. In base $3$, this means that the final $u+1$ digits of $m$ are between $$ \underbrace{11\dots112}_{u+1\text{ digits}} \text{ and } \underbrace{22\dots221}_{u+1 \text{ digits}} $$ which is equivalent to at least one of and not all of $d_i$ being $2$ for $i\le u+2$, and the leftmost such digit being preceded by a string of all $1$'s (perhaps of length $0$). Equivalently, we could say that $u$ is absent from the sum if and only if either the final $u+1$ digits of $m$ are all $2$, or, among the last $u+1$ digits there is $0$ somewhere to the left of the first $2$. Thus $\ell_m=0$ if and only if either $m$ has no $2$ in its ternary expansion, or if the leftmost $2$ of $m$'s ternary expansion is preceded by a $0$ and all subsequent digits are $2$. Therefore, if $n=3m+2$, we have this property if and only if (in ternary) either $n-1$ or $n+1$ has no $2$.