, 2009

Consider $j$-th term in the above sum. It is equal to
$(\text{the coefficient of } x^j \text{ in } (1+2x)^{3n+2-j}) - (\text{the coefficient of } x^{j-1} \text{ in } (1+2x)^{3n+1-j})$.
This in turn is equal to
$$\text{the coefficient of } x^{3n+2} \text{ in } x^{3n+2-j} \left( (1+2x)^{3n+2-j} - x(1+2x)^{3n+1-j} \right).$$
A little simplification shows that this is equal to
the coefficient of $x^{3n+2}$ in $(x+x^2)(x+2x^2)^{3n+1-j}$.

Thus the sum above is equal to the coefficient of $x^{3n+2}$ in
$$x(1+x)((x+2x^2)^{3n+1} + (x+2x^2)^{3n} + \dots + (x+2x^2)^{2n+1}).$$
The last expression reduces to
$$x^{2n+2}(1+2x)^{2n+1} \frac{1-(x+2x^2)^{n+1}}{1-2x}.$$
Now the second term in the above product does not contribute to the coefficient of $x^{3n+2}$. Hence this coefficient is precisely equal to the coefficient of $x^n$ in
$$\frac{(1+2x)^{2n+1}}{1-2x}.$$
Using binomial expansion for $1/(1-2x)$, this may be seen to be equal to
$$2^n \left( 1 + \binom{2n+1}{1} + \binom{2n+1}{2} + \dots + \binom{2n+1}{n} \right).$$
This is precisely
$$2^n \frac{1}{2} \left( \sum_{j=0}^{2n+1} \binom{2n+1}{j} \right).$$
which reduces to $2^{3n}$.