Question: I've been struggling with the following task for two days.

> 
> Find the number of sequences of length $2n$, with elements taken from the set $\{1,\ldots,2n\}$, such that no two neighboring elements sum up to $2n.$
> 
> 
> For example, for $n = 2$:
> 
> 
> 1112 $\to$ good  
> 
> 1231 $\to$ wrong (because $3+1 = 4 = 2n$)
> 
> 
> 

I've tried to do it using the Inclusion–Exclusion Principle and recursion but always end up with so many cases to consider that I give up. Since this was a test question on last year's test, it can't be so complicated.

It would be great if someone could give me a hint how to solve it.

Answer: 
The step you do not understand is
$$\frac{(x+1)}{6} x(2x+1) + \frac{6(x+1)^2}{6}=\frac{x+1}{6}[x(2x+1)+6(x+1)]$$
is it?

In this step you just have to *factor out* the term $\frac16(x+1)$ 

First write $(x+1)^2$ as $(x+1)(x+1)$
$$\frac{(x+1)}{6} x(2x+1) + \frac{6\color{red}{(x+1)^2}}{6}= \frac{(x+1)}{6} x(2x+1) + \frac{6\color{red}{(x+1)(x+1)}}{6}$$

Now you are able to factor out the term $\frac16(x+1)$

$$\color{red}{\frac{(x+1)}{6}} x(2x+1) + \frac{6\color{red}{(x+1)}(x+1)}{\color{red}{6}} = \color{red}{\frac{(x+1)}6}\cdot\left[x(2x+1)+6(x+1) \right]$$
Indeed, we have $$\frac{x}{6}(x+1)(2x+1)+(x+1)^2\to(x+1)\left[\frac{x}{6}(2x+1)+(x+1)\right]\\ =(x+1)\left[\frac{2x^2+x}{6}+(x+1)\right]=(x+1)\left[\frac{2x^2+x+6x+6}{6}\right]=(x+1)\left[\frac{2x^2+7x+6}{6}\right]$$ and for the final polynomial $2x^2+7x+6$ we have $2x^2+7x+6=(x+3/2)(x+2)$.