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

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!

-
You really could not see a pattern? – Mariano Suárez-Alvarez Feb 12 '13 at 6:12

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)$?

-

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}$$

-

I believe this is the right answer:

$$\\ T(n) = T(n - 3) + \frac{1}{2} \\ T(n) = T(n - 6) + \frac{1}{2} + \frac{1}{2} = T(n - 6) + \frac{2}{2} \\ T(n) = T(n - 9) + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = T(n - 9) + \frac{3}{2} \\ T(n) = T(n - 12) + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = T(n - 12) + \frac{4}{2} \\ ... \\ T(n) = T(n - k) + \frac{k}{3} \times \frac{1}{2} \\ \text{When }n - k = 0 \Rightarrow n = k \\ T(n) = T(0) + \frac{n}{3} \times \frac{1}{2} \\ \text{Hence, } T(n)\ \epsilon \ O(n)$$

-
Why come back to this? Especially to pretend that $T(n)$ and $T(0)$ are related when $n$ is not a multiple of $3$ (they are not). – Did Mar 9 '14 at 16:05

The generating function is $$g(x)=\sum_{n\ge 0}T(n)x^n = \frac{2-x^3}{2(1+x+x^2)(1-x)^2}$$, which has the partial fraction representation $$g = \frac{2}{3(1-x)} + \frac{1}{6(1-x)^2}+\frac{x+1}{6(1+x+x^2)}$$. The first term contributes $$\frac{2}{3}(1+x+x^2+x^3+\ldots)$$, equivalent to $T(n)=2/3$ the second term contributes $$\frac{1}{6}(1+2x+3x^2+4x^3+\ldots)$$ equivalent to $T(n) = (n+1)/6$, and the third term contributes $$\frac{1}{6}(1-x^2+x^3-x^5+x^6-\ldots)$$ equivalent to $T(n) = 1/6, 0, -1/6$ depending on $n\mod 3$ being 0 or 1 or 2. $$T(n) = \frac{2}{3}+\frac{n+1}{6}+\left\{\begin{array}{ll} 1/6,& n \mod 3=0\\ 0,& n \mod 3=1 \\ -1/6,&n \mod 3 =2\end{array}\right.$$

-