<s>[INST] 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!
 [/INST] 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)
$$
</s>