<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] 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}$$
</s>