Solving a tricky recurrence relation Given the following recurrence relation:


*

*$T_2=1$

*$T_4=4$

*$T_{2n}=
   \begin{cases}
    T_{2n-2}+3\bmod2n & 2T_{2n-2}\geq2n-2\\
    T_{2n-2}+2\bmod2n & 2T_{2n-2}  < 2n-2\\
   \end{cases}
  $
I need to find a closed-form expression for $T_{2n}$.
I have tried writing all the terms in the sequence but I can't seem to find a closed-form expression.
The problem is arising out of the extra condition.
How do I accommodate the value of $T_{2n-2}$ in order to solve this recurrence relation?
 A: I assume that when you say "$... \mod 2n$, you mean "the value congruent to $[...]$ modulo $2n$ which is in the range $1, 2, ... 2n$". We then have $T_4=T_{2\cdot2}=T_2+3=4$ which is indeed congruent to $4$ modulo $4$. Switching to the simpler notation $x_n = T_{2n}$, we have:
$$x_n=\begin{cases}
x_{n-1}+3 \mod 2n\quad \text{if $x_{n-1}\geq n-1$}\\
x_{n-1}+2 \mod 2n\quad \text{otherwise}
\end{cases}$$
When trying to generate $x_n$ from $x_{n-1}$, three numbers are important: the modulus ($2n$), the thing we compare $x_{n-1}$ to ($n-1$) and $x_{n-1}$ itself. Note that the modulus, being given by the formula $2n$, increases by $2$ at each stage. The comparandum, $n-1$, increases by $1$ at each stage. So let's say at some stage we have:
$$2n>x_{n-1}\geq n - 1$$
Note that the upper bound of $2n$ is always true since the modular operation in the recurrence implies $x_{n-1}\leq2(n-1)$. So now we're going to add $3$ to $x_{n-1}$, and repeat the process. Since the comparandum only increases by $1$, the sequence will still be greater than it, but because the modulus only increases by $2$, the sequence will "gain" on the modulus. We will therefore continue to add $3$ to the sequence until we "catch up" to the modulus, at which point the sequence will reset to $1$. Now we start adding $2$ to the sequence at each stage: it will thus start gaining on the comparandum (which is still only increasing by $1$), and this will continue until we "catch up" to it.
