Solution to the recurrence T(n) = 2T(n − 3)
It is easy to see the first nine terms of $\small T(n)$ is:

$$
\small
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\color{red}{T(1)} &amp; \color{blue}{T(2)} &amp; \color{olive}{T(3)} &amp; \color{red}{T(4)} &amp; \color{blue}{T(5)} &amp; \color{olive}{T(6)} &amp; \color{red}{T(7)} &amp; \color{blue}{T(8)} &amp; \color{olive}{T(9)} \\ \hline
1 &amp; 1 &amp; 1 &amp; 2 &amp; 2 &amp; 2 &amp; 4 &amp; 4 &amp; 4 \\ \hline
\end{array}
$$


  Observation: For integer $\small k \geq 0$, $\small T(3k+1) = T(3k+2) = T(3k+3)$. You can prove it by induction, where the base case is $\small T(1) = T(2) = T(3)= 1$. 


Given $\small n$, let $\small k$ be the smallest integer with $\small 3k \geq n$. In other words, $\small k = \lceil n / 3\rceil$. By the observation above, $\small T(n) = T(3k)$. Therefore, we have
$$
\small
T(n) = T(3k) = 2\cdot T(3(k-1)) = 2^2\cdot T(3(k-2)) = \cdots = 2^{k-1}T(3) = 2^{k-1} = 2^{\lceil n / 3\rceil - 1}
$$