# 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?

• What do you mean by "modulo $n$"? Do you mean that you calculate the expression on the right hand side of the equation, and then reduce it mod $n$ to a value in the range $0, 1, ... n-1$? – Jack M Oct 30 '15 at 12:51

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.