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!
 A: 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}$$
A: 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)$?
A: 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)
$$
A: 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.$$
