Counting number of possible sequences 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.
 A: The important point is that you can extend a sequence with any word except one, unless the last word is $2n$.  In that case you can extend it with any word. So let $A(m)$ be the number of sequences of length $m$ that end in $2n$ and $B(m)$ be the number of sequences of length $m$ that end in something else.  We have $$A(1)=1,B(1)=2n-1\\A(m)=A(m-1)+B(m-1)\\B(m)=2nA(m-1)+(2n-1)B(m-1)$$ and you want $A(2n)+B(2n)$
A: Hint:  The following approach is a little clumsy, but semi-mechanical.
We will change notation slightly. We will want to consider $n$ to be fixed, so it is more comfortable to call it $c$. The letter $n$ is now released for other duties. 
Call a word of length $n$, where the entries are chosen from $\{1,2,\dots, 2c\}$ good if no two consecutive letters add up to $2c$. 
Let $p_n$ be the number of good words of length $n$. We are only interested in $p_{2c}$, but finding $p_n$ seems more natural. 
Let $q_n$ be the number of good words of length $n$ that end in $2c$, and let $r_n$ be the number of good words of length $n$ that do not end in $2c$. Note that $p_n=q_n+r_n$. 
We have the following recurrences
$$q_{n+1}=q_n+r_n=p_n.\tag{1}$$
$$r_{n+1}=(2c-1)q_n +(2c-2)r_n=(2c-2)p_n+q_n.\tag{2}$$
In Recurrence (2), replace $r_{n+1}$ by $p_{n+1}-q_{n+1}$, and bump up indices by $1$. We get
$$p_{n+2}=(2c-2)p_{n+1}+q_{n+1} +q_{n+2}.$$
Now using (1) we get 
$$p_{n+2}=(2c-2)p_{n+1}+p_{n}+p_{n+1}=(2c-1)p_{n+1}+p_n.\tag{3}$$
 Finally, use standard techniques to solve (3). 
