Solving Recurrence $T(n) = T(n − 3) + 1/2$;

Question

I have to solve the following recurrence. $$\begin{gather} T(n) = T(n − 3) + 1/2\\ T(0) = T(1) = T(2) = 1. \end{gather}$$

I tried solving it using the forward iteration. $$\begin{align} T(3) &= 1 + 1/2\\ T(4) &= 1 + 1/2\\ T(5) &= 1 + 1/2\\ T(6) &= 1 + 1/2 + 1/2 = 2\\ T(7) &= 1 + 1/2 + 1/2 = 2\\ T(8) &= 1 + 1/2 + 1/2 = 2\\ T(9) &= 2 + 1/2 \end{align}$$

I couldnt find any sequence here. can anyone help!

Answer 1

It’s just three copies of a single recurrence interlaced with one another. The three copies are the sequences $\langle T(3n):n\in\Bbb N\rangle$, $\langle T(3n+1):n\in\Bbb N\rangle$, and $\langle T(3n+2):n\in\Bbb N\rangle$. Each looks just like the sequence defined by $S(0)=1$ and $S(n)=S(n-1)+\frac12$ for $n\ge 1$, which pretty clearly has the closed form $S(n)=\frac{n}2$.

How does $T(n)$ compare with $S\left(\left\lfloor\frac{n}3\right\rfloor\right)$?

Answer 2

The crucial observation is that the sequence occurs in blocks of 3, so for each $n$ we need to find out "which block of 3 is $n$ in". So using $\lfloor n/3\rfloor$ or $\lceil n/3\rceil$ would be good.

Observe the pattern: $$\begin{array}{c} n & T(n) & \lceil n/3\rceil\\\hline 0 & 2/2 & 1\\\hline 1 & 2/2 & 1\\\hline 2 & 2/2 & 1\\\hline 3 & 3/2 & 2\\\hline 4 & 3/2 & 2\\\hline 5 & 3/2 & 2\\\hline 6 & 4/2 & 3\\\hline 7 & 4/2 & 3\\\hline 8 & 4/2 & 3\\\hline \end{array}$$