1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$? $\endgroup$ – Jack M Oct 30 '15 at 12:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.