The induction approach is a good choice in this case, but we have to take into account the fact that, when passing from $n$ to $n+1$, only the first terms of the sequence can be left unchanged. For given $n$, the $n^{th}$ term is necessarily equal to $2n$, whereas for $n+1$ it has no fixed value and can range from $n$ to $2n+1$, depending on the distribution of the first $n-1$ terms. A method to solve this problem is to determine the change in the LHS and that in the RHS when passing from $n$ to $n+1$, trying to identify the case in which any increase in the LHS is minimized and any increase in the RHS is maximized (and vice versa for the decreasing components). If the inequality holds even in this worst scenario, it is true.
For $n=1$, the inequality is trivially satisfied. Passing from $n$ to $n+1$, there is a new term at the end of the sequence, given by $a_{n+1}=2n+2$. So the first component of LHS change is positive and given by
$$\Delta_{1}(LHS)=\binom{2n+2}{n+1}$$
However, we must take into account the above mentioned behaviour of the $n^{th}$ term. If this term decreases when passing to $n+1$, this creates a second component of change for the LHS, which tends to decrease it. In this regard, we can note that this decreasing component is maximal when the $n^{th}$ term changes from $2n$ to $n$, implying that the first $n-1$ terms are the integers from $1$ to $n-1$. In this case, the change in LHS is $$\Delta_2(LHS)=-\binom{2n}{n}+\binom{n}{n}=- \frac{n+1}{2(2n+1)} \binom{2n+2}{n+1} +1$$
On the other hand, passing from $n$ to $n+1$, the RHS changes by two components as well. Firstly, the summation of the first $n$ terms is no longer multiplied to $\binom{2n+1}{n}/(2^{2n+1})$, but to $\binom{2n+3}{n+1}/(2^{2n+3})$. Considering that the $n^{th}$ term changes from $2n$ to $n$, the RHS changes by
$$ \left[\dfrac{\binom{2n+3}{n+1}}{2^{2n+3}} - \dfrac{\binom{2n+1}{n}}{2^{2n+1}} \right] \sum_{i=1}^{n-1}2^{a_i} + \left[\dfrac{\binom{2n+3}{n+1}}{2^{2n+3}}2^n - \dfrac{\binom{2n+1}{n}}{2^{2n+1}}2^{2n} \right] $$
which can be simplified, after some hand calculations on factorials, as
$$\left[-\frac{1}{(n+2) 2^{2n+3}}\binom{2n+2}{n+1} \right]\sum_{i=1}^{n-1}2^{a_i} + \left( \frac{2n+3}{(n+2)2^{n+3}} -\frac{1}{4}\right)\binom{2n+2}{n+1}
$$
Note that both terms are negative, i.e. this component of the change in RHS leads to a decrease. Also note that the minimal decrease occurs when the first $n-1$ terms correspond to the integers between $1$ and $n-1$, as already assumed. In this case the summation of the first $n+1$ terms is $\sum_{i=1}^{n-1}2^{i} = 2^n-2$. So the last quantity can be rewritten as
$$\Delta_1(RHS)=\left[-\frac{1}{(n+2) 2^{n+3}} +
\frac{1}{(n+2) 2^{2n+2}} \right]
\binom{2n+2}{n+1} +
\left( \frac{2n+3}{(n+2)2^{n+3}} -\frac{1}{4}\right)\binom{2n+2}{n+1}
$$
In addition, the new $a_{n+1}=2n+2$ term at the end of the sequence generates in the RHS a positive quantity equal to
$$\Delta_2(RHS)=\dfrac{\binom{2n+3}{n+1}}{2^{2n+3}} 2^{2n+2}
= \dfrac{1}{2}\binom{2n+3}{n+1}\
= \frac{(2n+3)}{2(n+2)}\binom{2n+2}{n+1}$$
We can now collect all these results by taking the main terms of the $\Delta$ components (it is not difficult to show that the effect of the other terms is negligible and tends to zero as $n\rightarrow \infty$). Thus, passing from $n$ to $n+1$, we create a difference between the LHS and the RHS given by
$$\Delta_1(LHS)+\Delta_2(LHS)-\Delta_1(RHS)-\Delta_2(RHS)\\
=\left[1- \frac{n+1}{2(2n+1)} +\frac{1}{4} - \frac{(2n+3)}{2(n+2)} \right]\binom{2n+2}{n+1}
\\=
\left[\frac{5}{4}- \frac{5 n^2 + 11 n + 5}{4 n^2 + 10 n + 4} \right]\binom{2n+2}{n+1}
$$
The term in square brackets is always positive for positive $n$, and tends to $0$ as $n\rightarrow \infty$ (here is a plot). So, even in the worst scenario, passing from $n$ to $n+1$ we create a positive difference between the LHS and the RHS. This proves the inequality of the OP.
